基于图论的软件漏洞理论研究

As you may know, the fundamental causes of information insecurity in Internet are bugs of software, hardware or environments. Many efforts have been made to find and reduce bugs all over the world, but little progress has been obtained. This is may because the previous research focused only on searching bugs by matching features, without understanding bugs and the relations among the bugs. This project is aim to establish the fundamental theory of bugs and relations among bugs. The contents may include: (1) For every bug x, evaluate its harm f(x) based on concepts in graph theory and mathematical statistics. （2）For every pair of bugs x and y, define their dependence relation of harm g(x,y).And therefore establish bug relation graph. The useful tools to do this may be the concept kernel and kernel degree from graph theory. (3) With bug relation graph, we can find more bugs rapidly, using traditional feature matching algorithms. The results of this project will be very useful to construct a sound mathematical theory to obstacle some fundamental problem on bugs. Therefore the research is meaningful to information security.

众所周知，导致网络信息不安全的根源是软件、硬件以及环境等种种漏洞所致。虽然各国投入大量的人力物力从事软件漏洞的研究，但基本上都是以搜索匹配算法为主要手段展开研究，投资大量资源但效率低。其主要原因是对漏洞的基本属性，特别是漏洞之间的相关关联关系知之甚少。本项目的总体研究目标是：建立严谨的、较为完整的漏洞理论的体系结构。拟重点研究如下内容：①基于图论与统计分析等工具研究各种类型漏洞x，建立危害度函数f(x)，从理论上刻画漏洞的危险程度；②利用核度理论、图论、统计分析与随机函数建立两个漏洞x与y之间的关联关系强度函数g(x,y)，刻画漏洞分布所形成的网络结构特征；然后在此基础上建立漏洞网络图；③利用漏洞网络图与现有检测技术相结合，快速检测未知漏洞；研究成果将对漏洞的发现、传播及危害性控制等基本问题建立可靠的数学基础，从而对网络安全的发展起到不可估量的影响。

软件漏洞导致网络不安全，但怎么才能发现软件中的漏洞？虽然各国都投入了大量的人力物力来解决这个问题，但收效甚低。本项目的主要目标是研究软件漏洞的关联关系以及危害传播方式，以期更加高效地查找漏洞。本项目的主要成果有：1）用图论的方法建立了漏洞的关联关系模型，进而给出了相应的快速查找算法；2）在上述关系模型中，用统计方法对漏洞传播的危害值进行估计，给出了漏洞传播的统计模型、动力学模型、混沌模型，多种方法估计其危害性，以期更加准确地查出其危害性。.在该项目资助下，共发表论文20篇,其中EI引用论文8篇，SCI引用论文4篇,按计划顺利完成研究任务，达到预期目标，取得了丰硕成果。