一种支持动态信任评估的MapReduce调度方法

暂无

一种支持动态信任评估的MapReduce调度方法\n技术领域\n[0001] 本发明属于云计算环境的安全领域，涉及一种支持动态信任评估的MapReduce调度方法，主要应用在Hadoop的MapReduce计算框架之上。\n背景技术\n[0002] Hadoop不仅是一个用于存储的分布式文件系统，而且是设计用来在由通用计算设备组成的大型集群上执行分布式应用的框架，MapReduce是Hadoop的计算框架。MapReduce框架用于在分布式并行环境中处理海量数据的计算。它将一个任务分解成更多份细粒度的子任务，这些子任务在空闲的处理节点之间被调度和快速处理之后，最终通过特定的规则进行合并生成最终的结果，其处理模型有点类似于传统编程模型中的分解和归纳方法。\nMapReduce模型将分布式运算抽象成Map和Reduce两个步骤，从而实现高效的分布式应用。\n其中Map步骤负责根据用户输入的Key-Value对生成中间结果，中间结果同样采用Key-Value对的形式。Reduce步骤则将所有的中间结果根据Key进行合并，然后生成最终结果。而开发人员需要做的就是实现自己的Map和Reduce函数逻辑，然后提交给MapReduce运行环境。\n[0003] MapReduce的特点导致每个子任务的执行结果都可以影响最终的计算结果。目前云计算环境日益复杂，公有云和私有云融合在一起，分布式计算系统越来越开放，使得攻击者有机可乘，外部攻击者通过各种攻击手段得到某个或多个云计算集群节点的控制权，以及内部攻击者的存在，都威胁到了MapReduce的计算安全。对MapReduce的攻击，可归纳为两种欺骗形式：\n[0004] 欺骗1假设map函数为f，计算参与者(mapper)被分配一个split D，要求对所有D中的记录X∈D＝{x1，...，xn}，都进行f(x)计算。攻击者只对D的子集D’中的记录进行f计算，并声称已经对所有记录进行了map计算，通过heartbeat通知master任务已经完成。\n[0005] 欺骗2假设map函数为f，计算参与者(mapper)被分配一个split D，要求对所有D中的记录x∈D＝{x1，...，xn}，都进行f(x)计算。攻击者对D中的记录进行g计算，并声称已经对所有记录进行了f计算，通过heartbeat通知master任务已经完成。\n[0006] 根据攻击的手段的不同，可以将攻击者分为以下三类。\n[0007] 第一类是鲁莽攻击。攻击者控制mapper，总是返回错误的结果。对于这类攻击，只要对结果随机进行一次简单的验证，就可以发现攻击的存在。这种攻击，也是最容易识破和避免的。\n[0008] 第二类是普通攻击。攻击者以一定概率返回错误的结果。第一类攻击是本类攻击的一个极端情况(概率为100％)。这种攻击比较常见，比第一类攻击有更高的成功率，也更难以识破。对于此类攻击，可以采用voting的做法来验证结果的完整性，也就是分配多个mapper同时对一个split运算，map完成之后会对输出进行比较，如果多个mapper的结果都一样，则认为结果正确，如果有不同结果，则选取出现次数最多的结果作为正确结果。该做法的缺点是带来极大的性能损耗。\n[0009] 第三类是机智攻击。攻击者假设MapReduce的Job调度机制中有信任体系，在一段时间内一直返回正确的结果，直到系统放松对其的监察，甚至完全信任攻击者，会无保留的接受攻击者提供的结果。此时，攻击者才会返回错误的结果。这种攻击手段最为狡猾，也最难以防范。\n[0010] 攻击者采取的攻击方式可能会比上述更为复杂。攻击者可能控制了多个节点，这是更容易规避系统的检查。按照是否为有合作的攻击，攻击场景又可分为以下两种。\n[0011] 第一种是非合谋攻击。之前论述的攻击方式基本属于此类。在非合谋的模型下，攻击者只控制了一个worker，或者控制了多个worker，但是在攻击过程中每个worker都是独立执行，worker间并没有合作和互动。比如，一个攻击者控制了两个worker，两个worker被分配执行同一split上的同样的map操作，这两个worker都返回了错误的结果，但是这两个错误的结果却是不同的。\n[0012] 第二种是合谋攻击。攻击者控制了多个worker，其中一个worker的行为依赖于与其合谋的其他worker的行为。worker之间会存在信息的交换和沟通。该攻击主要应对系统采用replication或者voting进行结果完整性验证。replication是voting的一个特例，系统分配两个worker执行同样的计算，如果两个worker返回结果不同，则至少有一个是错误的。比如，攻击者控制了两个worker，master向worker分配任务后，两个worker可以知道它们是否被分配了相同的输入split。如果是相同的，它们可以返回相同的结果，但是该结果是错误的，这样就避免了被检测出来的风险。合谋攻击实施的难度较高，成功的概率较小，但是会带来非常大的威胁。\n[0013] 以上攻击的存在，使得制定出一套可以保证计算可信性的框架，即一种可信的MapReduce信任度量和调度策略显得尤为重要，这套策略既要兼容已有的应用程序，还要考虑到如何在不可信的节点上得到可信的计算结果。以下是目前可查到的与MapReduce中计算结果完整性保护和可信调度策略相关的专利情况。\n[0014] 公开号为US20090651100，发明名称为“SUSPICIOUS NODE DETECTION AND RECOVERY IN MAPREDUCE COMPUTING”的发明公开了一种检测和纠正云计算环境中恶意节点的方法，该方法采用嫌疑指数(suspicion index)，设置嫌疑阈值，在任务执行中检查节点的嫌疑指数是否超过该阈值，若超过则进行执行的恢复，否则接受节点执行的结果。\n[0015] 该专利虽然也涉及到恶意节点的检测，通过嫌疑阈值的设置来检测恶意节点，并根据此提供恶意节点的恢复但并没有针对MapReduce计算的完整性保护方面，其关注的焦点更多在于更普遍的攻击方式。\n[0016] 专利号为200910311687.X，发明名称为“一种基于MapReduce的自适应作业调度方法”的发明提供一种基于计算节点实际计算能力，具有自适应任务划分和任务调度的方法。\n该发明涉及分布式并行计算领域中MapReduce自适应作业调度方法，包括下列步骤：\nMapReduce计算各个计算节点单CPU内核的能力指数；计算MapReduce作业的数据块规模；调度节点对新进入的MapReduce作业的数据进行划分；调度节点动态将MapReduce作业的数据块组装成任务，分配给各计算节点；动态统计各计算节点的资源使用率，如果资源使用率低于门限，重新计算MapReduce作业的数据块规模。\n[0017] 该专利针对分布式系统中的计算和存储资源，将其按照资源使用率调度，解决的是MapReduce中计算性能的问题。虽然也是在MapReduce框架下对任务进行调度，但是该专利并不是一个从安全角度出发的专利，其重视的是解决分布式应用的效率问题。\n发明内容\n[0018] 针对MapReduce计算结果的完整性和可信性保证问题，当前并没有相关专利涉及。\n但是随着MapReduce在大数据处理领域越来越广泛的应用，提供一种可信的机制保证计算结果的可信性成为亟待满足的需求。本发明针对上述需求，基于现有MapReduce计算框架提出一种支持动态信任评估的调度方法，其重点是在灵活的结果完整性验证方案之上给出了被调度实体的动态信任评估体系。结果完整性验证方案采用测验验证(Quiz)和检查点验证(Checkpoint)方法相结合，二者相互补充，避免了误判和漏判，是整个系统的技术基础，两种验证方法可以选择性使用，提供了灵活性；信任评估体系基于上述完整性验证的结果，对信任这一抽象概念进行量化，并通过继承机制和反馈机制对信任值进行动态评估；调度策略则基于前二者，将信任作为调度考量因素加入MapReduce的调度器中，并对不同操作设置信任值阈值，从而达到性能和信任的最佳平衡。\n[0019] 以下重点阐述发明中的三个要点：\n[0020] 一、结果完整性验证：包括基于Quiz的结果完整性验证和基于Checkpoint的结果完整性。Quiz和正常计算任务没有区别，只不过Quiz的计算结果是可以验证的。基于Quiz的结果完整性验证基本思想是向正常任务中插入Quiz，计算的参与者无法区分Quiz的存在。\n通过对Quiz结果的验证，客户可以选择接受或者拒绝计算的结果。其具体做法是，设一个任务的大小为s，客户端选取t大小的任务，然后将t+m＝s大小的任务发送给计算执行者，其中m是Quiz。该任务完成后，客户检查隐藏的Quiz的计算结果是否正确。只有Quiz的结果正确，此次计算的结果才会被接受。否则，客户会将所有计算结果丢弃，重新调度和计算。Quiz数据由用户提供，或由系统按照用户定义的函数或规则自动的随机生成。Quiz数据直接通过代理插入到mapper的输入数据中，map计算完成后，对Quiz的计算结果进行比对验证。验证完成后，要剔除Quiz，通过对map的输出key/value的模式匹配定位Quiz的位置，然后将其从文件中删除。\n[0021] 基于Checkpoint的结果完整性验证中，系统采用冗余计算，将同一个任务分配给不在同一个节点的两个Worker执行。当Worker计算执行到输入文件的某个特定位置时(如第1行，第100行，第1000行)，以及到达某个关键位置(如一个文件不能够完全存储Worker输出数据需要写入新的文件时)，暂停Worker的执行，设定为Checkpoint。对于执行同一任务的两个Worker，选取相应的Checkpoint，对已有数据计算哈希值，然后系统比对该Checkpoint时二者的哈希值。如果两个哈希值相同，接受该Checkpoint的结果，计算继续进行；如果两个哈希值不同，则至少有一个结果是错误的，此时立即停止两个Worker的执行，重新选取两个Worker执行该任务。\n[0022] 系统采用Quiz和Checkpoint结合的验证方案，一个任务开始时，两个worker同时分配相同的正常任务和Quiz任务，在任务执行过程中进行Checkpoint的验证，若验证通过，则任务执行完成后进行Quiz的验证。如果所有Checkpoint哈希值的比对都是相同的，且Quiz的计算结果和期望的正确结果一致，则视为通过结果完整性验证，否则视为结果完整性验证失败。Checkpoint方案可以尽早发现非合谋攻击和部分合谋攻击的存在，对于合谋攻击，由于Quiz方案不依赖于任务复制，可以杜绝此种攻击的存在。而这结合的的优势是有效避免对各种攻击的漏判。\n[0023] 二、信任评估：将云计算系统中从数据中心、计算节点到进程不同信任级别的各实体按照物理或者逻辑上的包含关系，建立一种树状划分结构。一个实体(父实体)可以包含若干个其他实体(子实体)，如一个集群包含多个计算节点，一个计算节点包含多个进程。一个实体(子实体)只可以包含于某一个其他实体(父实体)(如一个进程包含于一个计算节点，一个计算节点包含于一个集群等)。图4为一个典型的云计算系统中实体之间的树状结构。\n[0024] 信任评估体系将信任这一抽象概念依据系统内实体的树状结构属性和它们的历史行为进行量化。发明中的信任有三个特点：一、可继承和反馈。继承机制是指，当一个新的实体加入系统时，其初始信任值继承于包含它的实体，即新加入的实体的信任值＝父实体的信任值*继承因子；反馈机制则是指，一个子实体的信任值变动会影响到其父实体的信任值，即父实体的新信任值＝父实体的原信任值+子实体的信任值变化量*反馈因子。二、信任是动态的，任何实体的信任值在其运行中受到评估而变化，同时相关实体的信任值通过继承和反馈机制是相互影响的，并且在系统运行中信任值随着时间而衰减，比如过了1小时，信任值减1，但是由于其他机制的存在，信任值整体也可能是增大的。三、信任具有生命周期，不同实体的信任生命周期不同。系统的重启，系统新的配置，系统管理员定义等都可以导致新的生命周期。\n[0025] 一个实体加入系统时开始其生命周期，引发信任值的初始化。对系统运行起管理作用的特殊实体，包括主节点(master节点)，验证节点(verifier节点)的信任值初始值首先通过系统设定值决定，服务提供依据经验赋予其一个基本值；对于其他由系统管理的实体(如mapper)其初始值受到继承机制的影响，父实体的信任值乘以影响因子后赋予给子实体。在实体的执行中，Quiz和Checkpoint方案会对执行结果进行完整性验证，通过验证给予信任奖励，增加该实体的信任值，反之则给予惩罚，减少该实体的信任值。该实体的信任值变化，通过反馈机制影响其父实体的信任值，依次类推，直到最高层的实体。\n[0026] 三、调度策略：系统的调度策略，在Hadoop原有调度策略的基础上，增加了信任的因素，确保所有任务都能得到可靠的执行，系统根据用户的输入和用户购买的服务不同将任务划分为不同优先级，对完整性敏感度高的关键任务，优先调度在信任高的实体上执行。\n系统对信任阈值和提交阈值进行设定，以满足客户对不同信任度的需求。\n[0027] 本发明的调度策略包括任务的懒惰提交(Lazy Committing)机制，任务回滚机制和信任调度机制。懒惰提交(Lazy Committing)机制是指一个实体的计算结果并非立刻提交，而是先放入全局缓冲区(GRB)，随着运算的执行，通过结果完整新验证(Quiz验证和Checkpoint验证)该实体如果一直正确执行则可以不断积累信任值，直到超过提交阈值(提交阈值是由系统设置的经验值，默认为统一值，但可以对某个实体单独设置)，该实体之前产生的结果才会提交，即Hadoop中mapper任务的提交，通知master任务执行完成，提交后该实体(worker)进入新的生命周期。若某个实体在结果完整性验证中被发现有作弊行为，其信任值根据系统的惩罚措施被减少，当该实体的信任值为负时，即表明该实体不可再被信任，该线程被终止，新的线程填充到线程池中等待调度。这就是回滚机制，回滚机制伴随着重新调度。\n[0028] 信任调度机制采用信任阈值作为调度的要求。信任阈值是一个特定的信任值，由服务提供商根据客户需求设定，在作业调度的时候，调度器只会给信任值高于作业信任阈值的信任实体分配任务。信任阈值越高，满足作业执行条件的实体就越少，执行结果越可信。系统分配更多的计算资源给信任值高的实体，并且尽量将信任阈值低的作业分配到信任值低的实体，以达到不同实体间的负荷平衡。同时，云服务提供商对外提供计算服务，信任阈值可以作为定价的一个标准。对可信要求高的用户可以选择购买更贵的服务来得到更高的信任阈值。\n[0029] 与现有技术相比，本发明的积极效果为：\n[0030] 一、提供了基于Quiz和Checkpoint的两种不同的结果完整性验证的方案，客户可以根据特定应用场景对方案进行选择，并且可以很容易加入新的结果完整性验证方案作为信任评估的依据，并不需要对整体框架进行改动，提供了灵活性；\n[0031] 二、以往的技术往往只将CPU、磁盘等作为调度的影响因素，本发明同时把信任量化，将信任作为影响作业调度的因素，可以有效防止包括合谋攻击在内的针对计算安全的攻击，并且达到性能和可信的平衡；\n[0032] 三、现有MapReduce程序不需修改或只需很小修改即可运行于本发明之上，具有对上和对下的兼容性。\n附图说明\n[0033] 图1为本发明的方法流程图；\n[0034] 图2为Quiz的生成途径流程图；\n[0035] 图3为Quiz的比对和去除流程图；\n[0036] 图4为一个典型的系统的信任集的树状结构。\n具体实施方式\n[0037] 下面结合附图对本发明的具体方法进行进一步详细描述。\n[0038] 本发明的方法流程如图1所示，本支持信任动态评估的MapReduce系统由master节点维护系统正确运行需要的信息，包括信任实体的树状结构，系统黑名单，信任阈值，提交阈值，继承因子，反馈因子，各个信任实体的信任值等，其中信任实体的信任值作为实体属性数据结构的一个字段在作业调度过程中动态修改。系统运行开始时首先对上述参数初始化，依据继承机制对各个实体的信任值进行计算并存储。初始值有预设的参考值，并受继承机制的影响。信任值的计算是在master上发生的。InitCredit()函数首先调用GetDomainParent()函数，得到要计算的实体的父实体。之后通过GetDomainCredit()函数，得到父实体的信任值。要计算的实体的信任值为包含它的父实体的信任值*继承因子。注意，当要计算的实体的父实体在黑名单上时，将不进行上述计算，而是直接赋值为-1，即加入黑名单。\n[0039] 当用户提交作业时，系统根据作业属性计算所需参数(作业的信任阈值，作业优先级)，调度策略遍历读取各实体信任值，找到信任值大于信任阈值的实体，即可调度实体集合。在所有可调度实体中，按照信任值进行从小到大排序，从排序的实体中选择排序靠前的足够的实体，使得这些实体的计算能力的估算值能够达到客户的要求，然后将作业在这些实体上按照原Hadoop调度因素(如距离)分配。\n[0040] 任务分配完成后开始执行，并对结果进行进行完整性验证。结果完整性验证采用基于Quiz和Checkpoint的方案，Quiz和checkpoint的结合，通过在所执行作业的原始数据和Hadoop中类RecordReader之间加入代理层ProxyReader来保证执行同样map任务的worker(可调度实体)输入数据是一样的。\n[0041] 基于Quiz的结果完整性验证中，Quiz的生成途径如图2所示有两种，一种是客户直接向系统提供Quiz数据，另一种是提供规则，由系统根据规则由随机数发生器产生，对于Quiz的每个字段，首先确认类型和范围，系统在所给的范围内随机生成。Quiz的插入由ProxyReader实现，系统在RecordReader和数据源之间加入一个数据读取的代理ProxyReader，ProxyReader工作和原有RecordReader相同，新的RecorReader相当于ProxyReader的一层包装，保证mapper读取数据的API没有改变。在ProxyReader里加入钩子函数，函数按照一定概率触发的，当函数触发时，ProxyReader的输出中(即map输入中)加入Quiz数据。RecordReader把ProxyReader作为唯一数据源，保证了执行同一任务的不同Worker输入是相同的。Quiz计算完成后，根据key/value对和期望结果进行模糊匹配，并根据匹配结果剔除(否则Quiz结果会影响后续计算)。Quiz的比对和去除如图3所示。Quiz在一个map任务执行完成后由master进行验证。\n[0042] Checkpoint的设定依赖于触发器函数CheckpointTrigger()和Freeze()函数。在RecordReader中加入CheckpointTrigger函数，Worker通过RecordReader类读取记录，当执行到checkpoint时，CheckpointTrigger()调用Freeze()函数，Freeze()函数向RecordReader发送PAUSE信号，暂停其对输入文件的读取，并等待已经读取的记录完成计算，之后完成哈希值的计算和比对。\n[0043] 信任评估体系根据上述结果完整性验证，对各个实体的信任值进行动态调整。若某个实体通过结果完整性验证(Quiz验证和Checkpoint验证均正确)，则触发CalCredit()函数增加该实体的信任值，该实体新的信任值＝该实体原信任值+信任奖励值，信任奖励值是系统定义的正值。一个实体的信任值的变化，通过反馈机制影响其父实体的信任值。系统中反馈机制由CreditFeedback()函数实现。每当一个实体的信任值发生变化是，就会触发该函数的执行。按照实体的逻辑层次划分，该函数是自下而上执行的。假设一个实体的信任值变化了a，CreditFeedback()被触发。它首先利用GetDomainParent()查出该实体的父实体，父实体新的信任值＝旧信任值+a*反馈因子。若该父实体为树状结构的根(没有父实体的实体)，则反馈结束，否则继续进行，直到达到根。所有实体的信任值的变化，又影响了调度策略下一次的行为。反之，若某个实体没有通过结果完整性验证(Quiz验证和Checkpoint验证至少有一个失败)，则视为攻击存在于该实体内部，该实体被列入黑名单，此次结果完整性验证的结果可以作为攻击分析的参照，当系统排除攻击后，可将该实体从黑名单拿下。\n整个系统强内聚，实现了支持动态信任评估的MapReduce调度策略。\n[0044] 此外，系统设立时间衰减函数。一些实体(如节点)生命周期较长，较久的历史行为对当前参考意义减弱，该实体的信任值会随着系统运行，每个一段时间在当前信任值上减去衰减值。衰减值也是由系统根据经验设置。\n[0045] 调度策略依赖于全局缓冲区(Global Result Buffer)和回滚函数，实现了懒惰提交(Lazy Committing)机制和任务回滚机制。本系统中mapper的计算结果并不是完成后立即通过Shuffle过程交付给reducer的，而是先放置在全局缓冲区(GRB，Global Result Buffer)中，GRB存储在master节点。放置通过函数RegisterGRB()完成。RegisterGRB()不进行真正的数据移动，只是在GRB中注册。Worker(mapper，执行MapReduce中的Map操作)的计算结果放置在节点的本地磁盘上，master并不知道数据的真正位置，存储在GRB中的注册项的位置和数据在磁盘中实际存储位置的转换通过位于从节点上的TaskTracker中的映射完成。注册完成后，GRB中就存在记录未提交结果的项。当一个worker积累的信任值超过提交阈值时，属于它的记录在GRB中的数据就会由函数TrustedSubmit()提交，进行之后的shuffle及reduce操作。如果该worker没有通过结果完整性验证，被列入黑名单，属于该worker的上一个提交点后的GRB中的内容都会被抛弃。RollBack()函数根据GRB中的记录，结合系统日志，判断哪一个或者哪几个任务没有正确完成。找到这些任务后，再向master发出通知，告知master这些任务需要重新调度，将这些任务放入任务池中等待下一次的调度。