| 主权项 |
基于关联规则挖掘的不可达路径检测方法，该基于关联规则挖掘的不可达路径检测方法包括获取数据集、基于关联规则挖掘的分支相关性的确定及不可达路径的检测，其特征在于，获取数据集，首先采用静态分析技术，利用Soot对程序进行预处理，构建程序的控制流图、控制树及蕴含树，然后设计搜索算法找出具有控制关系的分支节点序列集U，对于<img file="FDA0000754305920000011.GIF" wi="205" he="69" />采用动态分析技术，通过JDI监听序列u<sub>i</sub>中各个分支节点n<sub>i1</sub>,n<sub>i2</sub>,…,n<sub>ik</sub>的执行情况，在输入域内随机获取N个抽样输入向量，要求当程序输入每个抽样向量时n<sub>i1</sub>,n<sub>i2</sub>,…,n<sub>ik</sub>全部执行，若存在某节点n<sub>im</sub>不执行，则换取其它抽样值，直到所有的分支节点都执行；基于关联规则挖掘的分支相关性的确定，从数据集D<sub>i</sub>中，找出所有满足支持度大于等于最小支持度min_support的频繁项集，我们采用FP‑Growth算法进行挖掘，首先需要读取数据集D<sub>i</sub>，构造频繁1‑项集及FP‑Tree，然后根据算法2在FP‑Tree上进行频繁项集的挖掘，算法2采用分而治之的方法，它将FP‑Tree分解成一些条件模式库CPB，每个CPB和一个频繁1‑项集相关联，我们根据CPB构造其相应的条件FP‑tree，然后再采用递归算法分别对这些条件FP‑tree进行挖掘，从而得到所有的频繁项集F(D<sub>i</sub>,min_support)；利用上一步得到的频繁项集F(D<sub>i</sub>,min_support)来产生规则，如果某一规则的置信度大于等于最小置信度(min_confidence)，则该规则为关联规则，频繁项集{A,B}产生的规则<maths num="0001" id="cmaths0001"><math><![CDATA[<mrow><mi>A</mi><mo>⇒</mo><mi>B</mi><mo>,</mo></mrow>]]></math><img file="FDA0000754305920000012.GIF" wi="164" he="69" /></maths>每个关联规则的生成为，对于<maths num="0002" id="cmaths0002"><math><![CDATA[<mrow><mo>∀</mo><mi>f</mi><mo>∈</mo><mi>F</mi><mrow><mo>(</mo><msub><mi>D</mi><mi>i</mi></msub><mo>,</mo><mi>m</mi><mi>i</mi><mi>n</mi><mo>_</mo><mi>sup</mi><mi>p</mi><mi>o</mi><mi>r</mi><mi>t</mi><mo>)</mo></mrow><mo>,</mo></mrow>]]></math><img file="FDA0000754305920000013.GIF" wi="673" he="81" /></maths>产生f的所有非空子集；对于f的每一个非空子集v，若<maths num="0003" id="cmaths0003"><math><![CDATA[<mrow><mi>c</mi><mi>o</mi><mi>n</mi><mi>f</mi><mi>i</mi><mi>d</mi><mi>e</mi><mi>n</mi><mi>c</mi><mi>e</mi><mrow><mo>(</mo><mi>v</mi><mo>⇒</mo><mo>(</mo><mrow><mi>f</mi><mo>-</mo><mi>v</mi></mrow><mo>)</mo><mo>)</mo></mrow><mo>=</mo><mfrac><mrow><mi>P</mi><mrow><mo>(</mo><mi>f</mi><mo>)</mo></mrow></mrow><mrow><mi>P</mi><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow></mrow></mfrac><mo>=</mo><mfrac><mrow><mi>sup</mi><mtext> </mtext><mi>p</mi><mi>o</mi><mi>r</mi><mi>t</mi><mrow><mo>(</mo><mi>f</mi><mo>)</mo></mrow></mrow><mrow><mi>sup</mi><mtext> </mtext><mi>p</mi><mi>o</mi><mi>r</mi><mi>t</mi><mrow><mo>(</mo><mi>v</mi><mo>)</mo></mrow></mrow></mfrac><mo>≥</mo><mi>min</mi><mo>_</mo><mi>c</mi><mi>o</mi><mi>n</mi><mi>f</mi><mi>i</mi><mi>d</mi><mi>e</mi><mi>n</mi><mi>c</mi><mi>e</mi><mo>,</mo></mrow>]]></math><img file="FDA0000754305920000021.GIF" wi="1160" he="125" /></maths>其中P(f)表示f发生的概率，P(v)表示v发生的概率，则规则<img file="FDA0000754305920000022.GIF" wi="252" he="74" />为关联规则；不可达路径的检测，设n<sub>i</sub>和n<sub>j</sub>是程序中的两个条件语句，如果经关联规则挖掘后得到(n<sub>i</sub>,n<sub>j</sub>)有T→T相关性，则n<sub>i</sub>的真分支和n<sub>j</sub>的假分支构成冲突子路径；如果经关联规则挖掘后得到(n<sub>i</sub>,n<sub>j</sub>)有T→F相关性，则n<sub>i</sub>的真分支和n<sub>j</sub>的真分支构成冲突子路径；同样地，如果(n<sub>i</sub>,n<sub>j</sub>)有F→T相关性，则n<sub>i</sub>的假分支和n<sub>j</sub>的假分支构成冲突子路径；如果(n<sub>i</sub>,n<sub>j</sub>)有F→F相关性，则n<sub>i</sub>的假分支和n<sub>j</sub>的真分支构成冲突子路径；对于任何一条路径，若该路径包含冲突子路径，则它为不可达路径。 |
