A Game-theoretic Approach Towards Intelligent Insertion Of Software Vulnerabilities

The research on software vulnerability detection has attracted extensive attention in order to ensure the security of software.Fuzzing test is one of the most effective methods to discover software vulnerability.And software vulnerability corpora is an important basis to help researchers to evaluate and improve fuzzing test tools.However,the development of fuzzing test has been hampered due to the shortage of ground-truth corpora.To solve the problem,this paper presents a novel game-theoretic approach to intelligently compute the insertion locations and the complexities of software vulnerabilities to produce ground-truth corpora.The main idea of this paper is to cast the vulnerability insertion problem as a two-player zero-sum game between the corpora designer who inserts the exploitable,security-critical vulnerabilities and a fuzzing test tool who aims at detecting the vulnerabilities.Nash equilibrium of the game is adopted as the optimal solution for vulnerability insertion.Since the strategy spaces for both players are continuous and infinite,it is infeasible to use the traditional computing equilibrium algorithm.Hence,this paper proposes a BAR(Bundle-based Algorithm with Reduction)algorithm to compute the optimal solution efficiently.This algorithm is the first to propose a strategy reduction mechanism.Experiment results show the designer obtains a higher reward with the equilibrium strategy of the software vulnerability corpora generation model.Furthermore,experimental results indicate that BAR improves the performance significantly compared to the original Double-Oracle algorithm,especially when problems get even larger.This paper solves the vulnerabilities insertion problem from the security game theory perspective.It has important significance for the diversity of software vulnerability corpora and the development of software testing technology.Meanwhile,the research on the algorithm of security game theory has a certain significance for the development and application of game theory.