PatchDiscovery: Patch Presence Test for Identifying Binary Vulnerabilities Based on Key Basic Blocks

Software vulnerabilities are easily propagated through code reuses, which pose dire threats to software system security. Automatic patch presence test offers an effective way to detect whether vulnerabilities have been patched, which is significant for large-scale software system maintenance. However, most existing approaches cannot handle binary codes. They suffer from low accuracy and poor efficiency. None of them are resilient to version gap, function size, and patch size. To tackle the above problems, we propose PatchDiscovery, a patch presence test approach to identify binary vulnerabilities by extracting key basic blocks of patch and vulnerability as their signatures for patch discovery. We propose an efficient and accurate basic block matching method over the normalized and simplified control flow graphs (CFGs) of a vulnerable function (VF) and its patched function (PF) to precisely locate a vulnerability and a patch. Then, we conduct fine-grained patch-level analysis on the patch and the vulnerability to gain their key basic blocks as the signatures of PF and VF for patch presence test. Concretely, the key basic blocks of PF and VF are separately searched in a target function (TF) to identify whether the TF is more similar to PF or VF, i.e., patched or not. Extensive experiments based on two real-world binary datasets that contain 524 common vulnerabilities and exposures (CVEs) with 11607 target functions reveal that PatchDiscovery is very effective and efficient. It achieves 92.2\%92.2% F-measure and takes only 0.091s on average to test a target function. It is also resilient to version gap, patch size, and function size to a good extent. Moreover, it is outperforming the state-of-the-art works and has a much faster testing speed for large-scale patch detection. Moreover, PatchDiscovery achieves good performance in firmware vulnerability discovery scenario.