Optimization of dynamic spot-checking for collusion tolerance in grid computing

Grid computing provides a paradigm for performing computationally intensive tasks by shared resources in a parallel and distributed manner. These shared resources, however, can be misused by malicious users to sabotage running applications of others in some competing environments. Voting-based techniques are commonly applied to resist the sabotage. These techniques become ineffective in systems subject to collusion attacks, where malicious resources collectively sabotage a task by returning identical incorrect outputs. To tackle the collusion attacks the spot-checking technique has been utilized, in which spotter jobs with known correct outputs are sent to randomly-chosen resources to estimate their credibility based on a comparison of returned results and the correct outputs. This paper aims to maximize effectiveness of the spot-checking technique (i.e., minimize the wrong output probability) while satisfying constraints on the expected overhead through optimizing assignment procedure parameters. These parameters include the number of deployed spotter jobs, the number of resources examined by each spotter job, and the number of resources assigned to execute the genuine task. Different from existing research that has assumed fixed values for the latter two parameters, this paper models a novel dynamic assignment procedure in which these two parameters depend on the number of colluded malicious resources (CMRs) detected so far. Moreover, the total number of CMRs is assumed to be uncertain whereas the strategy of CMRs is assumed to be the most harmful. Solution to the proposed dynamic spot-checking optimization problem encompasses an iterative method that evaluates the probability of the genuine task failure (wrong output) and expected overhead. As illustrated through examples, the proposed dynamic spot-checking optimization outperforms the static spot-checking significantly.