Research On Quick Detection Methods Of Security Vulnerabilities In Large-scale PLD

PLD is one of the core chipsets of modern electronic equipment. Due to the existence ofPLD security vulnerability and its great harm to electronic equipment, the research on PLDsecurity vulnerability and detection methods is beneficial to discover and remove the securityvulnerability in digital device, which has great practical significance.Taking the research on National "863" Project (2009AA01Z434) as background, this thesisproposes a detecting method of PLD security vulnerabilities based on state transition diagram,according to the existing forms and characteristics of PLD security vulnerabilities. And the PLDsecurity vulnerability detection system is designed and realized.Major contributions and innovations endeavored in this thesis are as follows:1. The existing forms and characteristics of PLD are studied. Aiming at the issue that theexisting security vulnerability detection methods do not suit for PLD security vulnerabilitydetection, a security vulnerability detection method based on state transition diagram is proposed.The method combines the off-line reverse analysis with the on-line reverse analysis, deduces theset of suspicious states through analyzing the functional corpora and working set, and detectssecurity vulnerabilities hidden in PLD.2. Quick data collecting algorithm based on ring-tree with auto-reset is proposed. Thealgorithm designs auto-reset mechanism to solve the problem that the existing data collectingalgorithms cannot collect data from PLD with vulnerabilities completely, and proposes adynamic shortest path algorithm to solve the dynamic change problems of driver paths in thering-tree data collecting algorithm, which reduces the times of state transition and improves theefficiency of data collection. Experiment results show that quick data collecting algorithm basedon ring-tree with auto-reset not only realizes the correct collection of functional corpora data, butalso increases about9%of data collection efficiency than existing algorithms.3. Aiming at the deficiency of the layout of state transition diagram, such as node overlayand disheveled distribution of nodes, etc, an improved visualization layout algorithm IGVA isproposed. The alogorithm uses heuristic methods to compute the attractive and repulsive forcesin different stages, decreases the attractive forces between nodes to avoid node overlay at earlyiterations, decreases the repulsive forces of edges to optimize the distribution of nodes at finaliterations, which reduces the space using by the graph. The results show that IGVA solves thenode overlay problem and achieves the layout goal of state transition diagram.4. A security vulnerability detection algorithm for the isolated states and redundancyfunctions based on visualization technology is proposed. The algorithm takes graph theory, settheory as a foundation, makes the best use of the environment-dependent characteristic of PLDto realize the visualization detection of security vulnerabilities, reduces the number of statesduring the process of detection and improves the detection efficiency. The results show that thisalgorithm has achieved lower rate of erroneous judgement and missing judgement, and higheraccuracy of detection results than the security vulnerability detection method based on off-linestate stimulation detection and on-line state contrast. 5. A PLD security vulnerability detection system is designed and implemented. The systemcan implement data collection, visualization of state transition diagram and security vulnerabilitydetection, which has been applied in National "863" Project and confirmed by "863" ExpertGroup. The test results prove that quick detection method of security vulnerabilities inLarge-Scale PLD discussed in the thesis is correct and effective, and has high detectionefficiency and exact detection results.