skip to main content
research-article
Open access

Beyond Tests: Program Vulnerability Repair via Crash Constraint Extraction

Published: 10 February 2021 Publication History
  • Get Citation Alerts
  • Abstract

    Automated program repair is an emerging technology that seeks to automatically rectify program errors and vulnerabilities. Repair techniques are driven by a correctness criterion that is often in the form of a test suite. Such test-based repair may produce overfitting patches, where the patches produced fail on tests outside the test suite driving the repair. In this work, we present a repair method that fixes program vulnerabilities without the need for a voluminous test suite. Given a vulnerability as evidenced by an exploit, the technique extracts a constraint representing the vulnerability with the help of sanitizers. The extracted constraint serves as a proof obligation that our synthesized patch should satisfy. The proof obligation is met by propagating the extracted constraint to locations that are deemed to be “suitable” fix locations. An implementation of our approach (ExtractFix) on top of the KLEE symbolic execution engine shows its efficacy in fixing a wide range of vulnerabilities taken from the ManyBugs benchmark, real-world CVEs and Google’s OSS-Fuzz framework. We believe that our work presents a way forward for the overfitting problem in program repair by generalizing observable hazards/vulnerabilities (as constraint) from a single failing test or exploit.

    References

    [1]
    Rohan Bavishi, Hiroaki Yoshida, and Mukul R. Prasad. 2019. Phoenix: Automated data-driven synthesis of repairs for static analysis violations. In Proceedings of the 27th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE’19). ACM, New York, NY, 613--624.
    [2]
    Cristian Cadar, Daniel Dunbar, and Dawson R. Engler. 2008. KLEE: Unassisted and automatic generation of high-coverage tests for complex systems programs. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI’08), Vol. 8. 209--224.
    [3]
    Yan Cai and Lingwei Cao. 2016. Fixing deadlocks via lock pre-acquisitions. In Proceedings of the International Conference on Software Engineering (ICSE’16). ACM, New York, NY, 1109--1120.
    [4]
    Satish Chandra, Stephen J. Fink, and Manu Sridharan. 2009. Snugglebug: A powerful approach to weakest preconditions. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’09). ACM, New York, NY, 363--374.
    [5]
    Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark F. Wegman, and F. Kenneth Zadeck. 1991. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems 13 (1991), 451--490.
    [6]
    Leonardo Mendonça de Moura and Nikolaj Bjørner. 2008. Z3: An efficient SMT solver. In Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’08). 337--340.
    [7]
    Gregory J. Duck and Roland H. C. Yap. 2016. Heap bounds protection with low fat pointers. In Proceedings of the 25th International Conference on Compiler Construction. ACM, New York, NY, 132--142.
    [8]
    Gregory J. Duck, Roland H. C. Yap, and Lorenzo Cavallaro. 2017. Stack bounds protection with low fat pointers. In Network and Distributed System Security Symposium (NDSS’17).
    [9]
    Zhaohui Fu and Sharad Malik. 2006. On solving the partial MAX-SAT problem. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing. 252--265.
    [10]
    Qing Gao, Yingfei Xiong, Yaqing Mi, Lu Zhang, Weikun Yang, Zhaoping Zhou, Bing Xie, and Hong Mei. 2015. Safe memory-leak fixing for C programs. In Proceedings of the International Conference on Software Engineering (ICSE’15). IEEE, Los Alamitos, CA, 459--470.
    [11]
    Xiang Gao, Sergey Mechtaev, and Abhik Roychoudhury. 2019. Crash-avoiding program repair. In Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA’19). ACM, New York, NY, 8--18.
    [12]
    Xiang Gao and Abhik Roychoudhury. 2020. Interactive patch generation and suggestion. In Proceedings of the Automated Program Repair Workshop. 2.
    [13]
    Luca Gazzola, Daniela Micucci, and Leonardo Mariani. 2019. Automatic software repair: A survey. IEEE Transactions on Software Engineering 45, 1 (2019), 34--67.
    [14]
    Zhen Huang, Mariana D’Angelo, Dhaval Miyani, and David Lie. 2016. Talos: Neutralizing vulnerabilities with security workarounds for rapid response. In Proceedings of the 2016 IEEE Symposium on Security and Privacy (S8P). IEEE, Los Alamitos, CA, 618--635.
    [15]
    Zhen Huang, David Lie, Gang Tan, and Trent Jaeger. 2019. Using safety properties to generate vulnerability patches. In Proceedings of the 40th IEEE Symposium on Security and Privacy (S8P’19). 539--554.
    [16]
    Ivan Jager and David Brumley. 2010. Efficient Directionless Weakest Preconditions. Technical Report CMU-CyLab-10-002. CyLab, Carnegie Mellon University.
    [17]
    Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. 2010. Oracle-guided component-based program synthesis. In Proceedings of the 32nd International Conference on Software Engineering (ICSE’10). 215--224.
    [18]
    Jiajun Jiang, Yingfei Xiong, Hongyu Zhang, Qing Gao, and Xiangqun Chen. 2018. Shaping program repair space with existing patches and similar code. In Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA’18). ACM, New York, NY, 298--309.
    [19]
    Guoliang Jin, Wei Zhang, and Dongdong Deng. 2012. Automated concurrency-bug fixing. In Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI’12). 221--236.
    [20]
    Yalin Ke, Kathryn T. Stolee, Claire Le Goues, and Yuriy Brun. 2015. Repairing programs with semantic code search (T). In Proceedings of the IEEE/ACM International Conference on Automated Software Engineering (ASE’15). IEEE, Los Alamitos, CA, 295--306.
    [21]
    Anil Koyuncu, Kui Liu, Tegawendé F. Bissyandé, Dongsun Kim, Martin Monperrus, Jacques Klein, and Yves Le Traon. 2019. iFixR: Bug report driven program repair. In Proceedings of the 26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE’19).
    [22]
    Chris Lattner and Vikram Adve. 2004. LLVM: A compilation framework for lifelong program analysis and transformation. In Proceedings of the International Symposium on Code Generation and Optimization (CGO’04). IEEE, Los Alamitos, CA, 75.
    [23]
    Xuan-Bach D. Le, Duc-Hiep Chu, David Lo, Claire Le Goues, and Willem Visser. 2017. JFIX: Semantics-based repair of Java programs via symbolic PathFinder. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA’17). ACM, New York, NY, 376--379.
    [24]
    Xuan Bach D. Le, Ferdian Thung, David Lo, and Claire Le Goues. 2018. Overfitting in semantics-based automated program repair. Empirical Software Engineering 23, 5 (2018), 3007--3033.
    [25]
    Xuan-Bach D. Le, David Lo, and Claire Le Goues. 2016. History driven program repair. In Proceedings of the International Conference on Software Analysis, Evolution, and Reengineering (SANER’16). IEEE, Los Alamitos, CA, 213--224.
    [26]
    Claire Le Goues, Neal Holtschulte, Edward K. Smith, Yuriy Brun, Premkumar Devanbu, Stephanie Forrest, and Westley Weimer. 2015. The ManyBugs and IntroClass benchmarks for automated repair of C programs. IEEE Transactions on Software Engineering 41, 12 (2015), 1236--1256.
    [27]
    Claire Le Goues, ThanhVu Nguyen, Stephanie Forrest, and Westley Weimer. 2012. GenProg: A generic method for automatic software repair. IEEE Transactions on Software Engineering 38, 1 (2012), 54--74.
    [28]
    Claire Le Goues, Michael Pradel, and Abhik Roychoudhury. 2019. Automated program repair. Communications of the ACM 62, 12 (2019), 56--65.
    [29]
    Junhee Lee, Seongjoon Hong, and Hakjoo Oh. 2018. MemFix: Static analysis-based repair of memory deallocation errors for C. In Proceedings of the 26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE’18). ACM, New York, NY, 95--106.
    [30]
    Xia Li, Wei Li, Yuqun Zhang, and Lingming Zhang. 2019. DeepFL: Integrating multiple fault diagnosis dimensions for deep fault localization. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA’19). 169--180.
    [31]
    Chen Liu, Jinqiu Yang, Lin Tan, and Munawar Hafiz. 2013. R2Fix: Automatically generating bug fixes from bug reports. In Proceedings of the 2013 IEEE 6th International Conference on Software Testing, Verification, and Validation (ICST’13). IEEE, Los Alamitos, CA, 282--291.
    [32]
    Kui Liu, Anil Koyuncu, Tegawendé F. Bissyandé, Dongsun Kim, Jacques Klein, and Yves Le Traon. 2019. You cannot fix what you cannot find! An investigation of fault localization bias in benchmarking automated program repair systems. In Proceedings of the 2019 12th IEEE Conference on Software Testing, Validation, and Verification (ICST’19). IEEE, Los Alamitos, CA, 102--113.
    [33]
    Fan Long and Martin Rinard. 2016. Automatic patch generation by learning correct code. In Proceedings of the ACM Symposium on Principles of Programming Languages (POPL’16).
    [34]
    Sergey Mechtaev, Xiang Gao, Shin Hwei Tan, and Abhik Roychoudhury. 2018. Test-equivalence analysis for automatic patch generation. ACM Transactions on Software Engineering and Methodology 27, 4 (2018), 1--37.
    [35]
    Sergey Mechtaev, Alberto Griggio, Alessandro Cimatti, and Abhik Roychoudhury. 2018. Symbolic execution with existential second-order constraints. In Proceedings of the 26th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE’18). ACM, New York, NY.
    [36]
    Sergey Mechtaev, Manh-Dung Nguyen, Yannic Noller, Lars Grunske, and Abhik Roychoudhury. 2018. Semantic program repair using a reference implementation. In Proceedings of the International Conference on Software Engineering (ICSE’18). 129--139.
    [37]
    Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2015. DirectFix: Looking for simple program repairs. In Proceedings of the 37th International Conference on Software Engineering (ICSE’15). IEEE, Los Alamitos, CA, 448--458.
    [38]
    Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2016. Angelix: Scalable multiline program patch synthesis via symbolic analysis. In Proceedings of the 38th International Conference on Software Engineering. ACM, New York, NY, 691--701.
    [39]
    Hong Mei and Lu Zhang. 2018. Can big data bring a breakthrough for software automation? Science China Information Sciences 61, 5 (2018), 056101.
    [40]
    Martin Monperrus. 2018. Automatic software repair: A bibliography. ACM Computing Surveys 51, 1 (2018), Article 17, 24 pages.
    [41]
    Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra. 2013. SemFix: Program repair via semantic analysis. In Proceedings of the 35th International Conference on Software Engineering (ICSE’13). IEEE, Los Alamitos, CA, 772--781.
    [42]
    Yuhua Qi, Xiaoguang Mao, Yan Lei, Ziying Dai, and Chengsong Wang. 2014. The strength of random search on automated program repair. In Proceedings of the 36th International Conference on Software Engineering (ICSE’14). 254--265.
    [43]
    Thomas Reps, Thomas Ball, Manuvir Das, and James Larus. 1997. The use of program profiling for software maintenance with applications to the year 2000 problem. In Proceedings of the 6th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE’97). 432--449.
    [44]
    Abhik Roychoudhury and Yingfei Xiong. 2019. Automated program repair: A step towards software automation. Science China Information Sciences 62, 10 (2019), 200103.
    [45]
    Ripon K. Saha, Yingjun Lyu, Hiroaki Yoshida, and Mukul R. Prasad. 2017. ELIXIR: Effective object oriented program repair. In Proceedings of the IEEE/ACM International Conference on Automated Software Engineering (ASE’17). IEEE, Los Alamitos, CA, 648--659.
    [46]
    Konstantin Serebryany, Derek Bruening, Alexander Potapenko, and Dmitriy Vyukov. 2012. AddressSanitizer: A fast address sanity checker. In Proceedings of the 2012 USENIX Annual Technical Conference (USENIX’12). 309--318.
    [47]
    Edward K. Smith, Earl T. Barr, Claire Le Goues, and Yuriy Brun. 2015. Is the cure worse than the disease? Overfitting in automated program repair. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering (FSE’15). ACM, New York, NY, 532--543.
    [48]
    Frank Tip. 1995. A survey of program slicing techniques. Journal of Programming Languages 3, 3 (1995), 121--189.
    [49]
    Rijnard van Tonder and Claire Le Goues. 2018. Static automated program repair for heap properties. In Proceedings of the International Conference on Software Engineering (ICSE’18). ACM, New York, NY, 151--162.
    [50]
    Bugzilla. 2019. Home Page. Retrieved July 20, 2019 from http://bugzilla.maptools.org/.
    [51]
    OSS-Fuzz. 2019. Home Page. Retrieved May 22, 2019 from https://bugs.chromium.org/p/oss-fuzz.
    [52]
    CVE. 2019. Home Page. Retrieved May 20, 2019 from https://cve.mitre.org/.
    [53]
    Clang 12. 2019. UndefinedBehaviorSanitizer. Retrieved July 20, 2019 from https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html.
    [54]
    Ming Wen, Junjie Chen, Rongxin Wu, Dan Hao, and Shing-Chi Cheung. 2018. Context-aware patch generation for better automated program repair. In Proceedings of the International Conference on Software Engineering (ICSE’18). ACM, New York, NY, 1--11.
    [55]
    Xiaoyuan Xie, Tsong Yueh Chen, Fei-Ching Kuo, and Baowen Xu. 2013. A theoretical analysis of the risk evaluation formulas for spectrum-based fault localization. ACM Transactions on Software Engineering and Methodology 22, 4 (2013), 1--40.
    [56]
    Qi Xin and Steven P. Reiss. 2017. Identifying test-suite-overfitted patches through test case generation. In Proceedings of the ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA’17). ACM, New York, NY, 226--236.
    [57]
    Yingfei Xiong, Xinyuan Liu, Muhan Zeng, Lu Zhang, and Gang Huang. 2018. Identifying patch correctness in test-based program repair. In Proceedings of the International Conference on Software Engineering (ICSE’18). ACM, New York, NY, 789--799.
    [58]
    Yingfei Xiong, Jie Wang, Runfa Yan, Jiachen Zhang, Shi Han, Gang Huang, and Lu Zhang. 2017. Precise condition synthesis for program repair. In Proceedings of the International Conference on Software Engineering (ICSE’17). IEEE, Los Alamitos, CA, 416--426.
    [59]
    X. Xu, Y. Sui, H. Yan, and J. Xue. 2019. VFix: Value-flow-guided precise program repair for null pointer dereferences. In Proceedings of the 2019 IEEE/ACM 41st International Conference on Software Engineering (ICSE’19). 512--523.
    [60]
    Jifeng Xuan, Matias Martinez, Favio Demarco, Maxime Clement, Sebastian Lamelas Marcote, Thomas Durieux, Daniel Le Berre, and Martin Monperrus. 2016. Nopol: Automatic repair of conditional statement bugs in Java programs. IEEE Transactions on Software Engineering 43, 1 (2016), 34--55.
    [61]
    Jinqiu Yang, Alexey Zhikhartsev, Yuefei Liu, and Lin Tan. 2017. Better test cases for better automated program repair. In Proceedings of the 11th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE’17). ACM, New York, NY, 831--841.
    [62]
    Zuoning Yin, Ding Yuan, Yuanyuan Zhou, Shankar Pasupathy, and Lakshmi Bairavasundaram. 2011. How do fixes become bugs? In Proceedings of the ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE’11). ACM, New York, NY, 26--36.

    Cited By

    View all
    • (2024)Multi-mechanism neural machine translation framework for automatic program repairJournal of Intelligent & Fuzzy Systems10.3233/JIFS-23403746:4(7859-7873)Online publication date: 18-Apr-2024
    • (2024)Detecting, Creating, Repairing, and Understanding Indivisible Multi-Hunk BugsProceedings of the ACM on Software Engineering10.1145/36608281:FSE(2747-2770)Online publication date: 12-Jul-2024
    • (2024)Unveiling ChatGPT's Usage in Open Source Projects: A Mining-based StudyProceedings of the 21st International Conference on Mining Software Repositories10.1145/3643991.3644918(571-583)Online publication date: 15-Apr-2024
    • Show More Cited By

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Software Engineering and Methodology
    ACM Transactions on Software Engineering and Methodology  Volume 30, Issue 2
    Continuous Special Section: AI and SE
    April 2021
    463 pages
    ISSN:1049-331X
    EISSN:1557-7392
    DOI:10.1145/3446657
    • Editor:
    • Mauro Pezzè
    Issue’s Table of Contents
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 10 February 2021
    Accepted: 01 August 2020
    Revised: 01 June 2020
    Received: 01 December 2019
    Published in TOSEM Volume 30, Issue 2

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Automated program repair
    2. constraint extraction and propagation
    3. overfitting

    Qualifiers

    • Research-article
    • Research
    • Refereed

    Funding Sources

    • National Research Foundation (NRF) Singapore
    • National Cybersecurity R8D (NCR) programme
    • National Satellite of Excellence in Trustworthy Software Systems
    • National Natural Science Foundation of China
    • Natural Science Foundation of Guangdong Province

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)743
    • Downloads (Last 6 weeks)65
    Reflects downloads up to 14 Aug 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Multi-mechanism neural machine translation framework for automatic program repairJournal of Intelligent & Fuzzy Systems10.3233/JIFS-23403746:4(7859-7873)Online publication date: 18-Apr-2024
    • (2024)Detecting, Creating, Repairing, and Understanding Indivisible Multi-Hunk BugsProceedings of the ACM on Software Engineering10.1145/36608281:FSE(2747-2770)Online publication date: 12-Jul-2024
    • (2024)Unveiling ChatGPT's Usage in Open Source Projects: A Mining-based StudyProceedings of the 21st International Conference on Mining Software Repositories10.1145/3643991.3644918(571-583)Online publication date: 15-Apr-2024
    • (2024)Out of Sight, Out of Mind: Better Automatic Vulnerability Repair by Broadening Input Ranges and SourcesProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639222(1-13)Online publication date: 20-May-2024
    • (2024)Constraint Based Program Repair for Persistent Memory BugsProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3639204(1-12)Online publication date: 20-May-2024
    • (2024)Pre-Trained Model-Based Automated Software Vulnerability Repair: How Far are We?IEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2023.330889721:4(2507-2525)Online publication date: Jul-2024
    • (2024)Prompt Fix: Vulnerability Automatic Repair Technology Based on Prompt Engineering2024 International Conference on Computing, Networking and Communications (ICNC)10.1109/ICNC59896.2024.10556123(116-120)Online publication date: 19-Feb-2024
    • (2024)On the acceptance by code reviewers of candidate security patches suggested by Automated Program Repair toolsEmpirical Software Engineering10.1007/s10664-024-10506-z29:5Online publication date: 3-Aug-2024
    • (2024)Enhanced evolutionary automated program repair by finer‐granularity ingredients and better search algorithmsJournal of Software: Evolution and Process10.1002/smr.262436:6Online publication date: 5-Jun-2024
    • (2023)A Survey of Learning-based Automated Program RepairACM Transactions on Software Engineering and Methodology10.1145/363197433:2(1-69)Online publication date: 23-Dec-2023
    • Show More Cited By

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    HTML Format

    View this article in HTML Format.

    HTML Format

    Get Access

    Login options

    Full Access

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media