2022

Automatically Mitigating Vulnerabilities in Binary Programs via Partially Recompilable Decompilation

Reiter, Pemma, Tay, Hui Jun, Weimer, Westley et al.

Understand

Vulnerabilities are challenging to locate and repair, especially when source code is unavailable and binary patching is required.

Manual methods are time-consuming, require significant expertise, and do not scale to the rate at which new vulnerabilities are discovered.
Automated methods are an attractive alternative, and we propose Partially Recompilable Decompilation (PRD).
PRD lifts suspect binary functions to source, available for analysis, revision, or review, and creates a patched binary using source- and binary-level techniques.

Built on

M. Hutchins, H. Foster, T. Goradia, and T. Ostrand, “Experiments on the effectiveness of dataflow-and control-flow-based test adequacy criteria,” in ICSE . IEEE, 1994
1994
Earlier work this paper cites.
J. R. Larus and E. Schnarr, “Eel: machine-independent executable editing,” in Programming language design and implementation . ACM, 1995
1995
Earlier work this paper cites.
J. A. Jones, M. J. Harrold, and J. Stasko, “Visualization of test information to assist fault localization,” in ICSE . IEEE, 2002
2002
Earlier work this paper cites.
C.-K. Luk, R. Cohn, R. Muth, H. Patil, A. Klauser, G. Lowney, S. Wallace, V. J. Reddi, and K. Hazelwood, “Pin: Building customized program analysis tools with dynamic instrumentation,” in Programming language Design and Implementation (PLDI ’05) , 2005
2005
Earlier work this paper cites.
N. Nethercote and J. Seward, “Valgrind: a framework for heavyweight dynamic binary instrumentation.” ACM, 2007
2007
Earlier work this paper cites.
R. Abreu, P. Zoeteweij, R. Golsteijn, and A. J. Van Gemund, “A practical evaluation of spectrum-based fault localization,” Journal of Systems and Software , 2009
2009
Earlier work this paper cites.
R. Abreu, P. Zoeteweij, and A. J. Van Gemund, “Spectrum-based multiple fault localization,” in Int. Conf. on Automated Software Engineering . IEEE, 2009
2009
Earlier work this paper cites.
M. Orlov and M. Sipper, “Genetic programming in the wild: evolving unrestricted bytecode,” in Genetic and Evolutionary Computation Conference . ACM, 2009
2009
Earlier work this paper cites.
W. Masri, “Fault localization based on information flow coverage,” Software Testing, Verification and Reliability , 2010
2010
Earlier work this paper cites.
S. Lin, “Rank aggregation methods,” Wiley Interdisciplinary Reviews: Computational Statistics , 2010
2010
Earlier work this paper cites.
E. Schulte, S. Forrest, and W. Weimer, “Automated program repair through the evolution of assembly code,” in Int. Conf. on Automated Software Engineering . ACM, 2010
2010
Earlier work this paper cites.
C. Le Goues, T. Nguyen, S. Forrest, and W. Weimer, “Genprog: A generic method for automatic software repair,” Ieee transactions on software engineering , 2011
2011
Earlier work this paper cites.
L. Naish, H. J. Lee, and K. Ramamohanarao, “A model for spectra-based software diagnosis,” ACM Transactions on software engineering and methodology (TOSEM) , 2011
2011
Earlier work this paper cites.
J. Lee, T. Avgerinos, and D. Brumley, “TIE: Principled Reverse Engineering of Types in Binary Programs,” in Network and Distributed System Security , 2011
2011
Earlier work this paper cites.
Z. Yin, D. Yuan, Y. Zhou, S. Pasupathy, and L. Bairavasundaram, “How do fixes become bugs?” in Foundations of Software Engineering . ACM, 2011
2011
Earlier work this paper cites.
C. Le Goues, M. Dewey-Vogt, S. Forrest, and W. Weimer, “A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each,” in ICSE . IEEE, 2012
2012
Earlier work this paper cites.
E. Schulte, J. DiLorenzo, W. Weimer, and S. Forrest, “Automated repair of binary and assembly programs for cooperating embedded devices,” ACM SIGARCH Computer Architecture News , 2013
2013
Earlier work this paper cites.
W. Weimer, Z. P. Fry, and S. Forrest, “Leveraging program equivalence for adaptive program repair: Models and first results,” in Int. Conf. on Automated Software Engineering (ASE) . IEEE, 2013
2013
Earlier work this paper cites.
W. E. Wong, V. Debroy, R. Gao, and Y. Li, “The dstar method for effective software fault localization,” IEEE Transactions on Reliability , 2013
2013
Earlier work this paper cites.
D. Bruening and T. Garnett, “Building dynamic instrumentation tools with dynamorio,” in Proc. Int. Conf. IEEE/ACM Code Generation and Optimization (CGO), Shen Zhen, China , 2013
2013
Earlier work this paper cites.
E. Schulte, J. DiLorenzo, W. Weimer, and S. Forrest, “Automated repair of binary and assembly programs for cooperating embedded devices,” ACM SIGARCH Computer Architecture News , 2013
2013
Earlier work this paper cites.
E. Schwartz, J. Lee, M. Woo, and D. Brumley, “Native x86 Decompilation using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring,” in USENIX . USENIX, 2013
2013
Earlier work this paper cites.
R. P. A. de Araujo and M. L. Chaim, “Data-flow testing in the large,” in Int. Conf. on Software Testing, Verification and Validation . IEEE, 2014
2014
Earlier work this paper cites.
V. Le, M. Afshari, and Z. Su, “Compiler validation via equivalence modulo inputs,” ACM Sigplan Notices , 2014
2014
Earlier work this paper cites.
Y. Qi, X. Mao, Y. Lei, Z. Dai, and C. Wang, “The strength of random search on automated program repair,” in ICSE . ACM Press, 2014
2014
Earlier work this paper cites.

Similar

K. Yakdan, S. Eschweiler, E. Gerhards-Padilla, and M. Smith, “No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations,” 2015
2015
Cited alongside, same era.
J. Song and J. Alves-Foss, “The darpa cyber grand challenge: A competitor’s perspective,” IEEE Security Privacy , 2015
2015
Cited alongside, same era.
E. K. Smith, E. T. Barr, C. Le Goues, and Y. Brun, “Is the cure worse than the disease? overfitting in automated program repair,” in Foundations of Software Engineering . ACM, 2015
2015
Cited alongside, same era.
E. M. Schulte, W. Weimer, and S. Forrest, “Repairing cots router firmware without access to source code or test suites: A case study in evolutionary software repair,” in Genetic and Evolutionary Computation Conference . ACM, 2015
2015
Cited alongside, same era.
Z. Qi, F. Long, S. Achour, and M. Rinard, “An analysis of patch plausibility and correctness for generate-and-validate patch generation systems,” in Int. Symp. on Software Testing and Analysis (ISSTA) . ACM Press, 2015
2015
Cited alongside, same era.
F. Long and M. Rinard, “Staged program repair with condition synthesis.” ACM Press, 2015
2015
Cited alongside, same era.
S. Sidiroglou-Douskos, E. Lahtinen, F. Long, and M. Rinard, “Automatic error elimination by horizontal code transfer across multiple applications,” in Programming Language Design and Implementation . ACM, 2015
2015
Cited alongside, same era.
F. Long and M. Rinard, “Automatic patch generation by learning correct code,” in ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages . ACM, 2016
2016
Cited alongside, same era.
M. Noonan, A. Loginov, and D. Cok, “Polymorphic type inference for machine code,” in Programming Language Design and Implementation , 2016
2016
Cited alongside, same era.
S. Mechtaev, J. Yi, and A. Roychoudhury, “Angelix: Scalable multiline program patch synthesis via symbolic analysis,” in ICSE , 2016
2016
Cited alongside, same era.
M. Noonan, A. Loginov, and D. Cok, “Polymorphic Type Inference for Machine Code,” in Programming Language Design and Implementation . Santa Barbara, CA: ACM Press, 2016
2016
Cited alongside, same era.
H. Zhu, T. Peng, L. Xiong, and D. Peng, “Fault localization using function call sequences,” Procedia Computer Science , 2017
2017
Cited alongside, same era.

Then

Y. Shoshitaishvili, A. Bianchi, K. Borgolte, A. Cama, J. Corbetta, F. Disperati, A. Dutcher, J. Grosen, P. Grosen, A. Machiry, C. Salls, N. Stephens, R. Wang, and G. Vigna, “Mechanical phish: Resilient autonomous hacking,” IEEE Security and Privacy , 2018
2018
Later among the works it cites.
A. Nguyen-Tuong, D. Melski, J. W. Davidson, M. Co, W. Hawkins, J. D. Hiser, D. Morris, D. Nguyen, and E. Rizzi, “Xandra: An autonomous cyber battle system for the cyber grand challenge,” IEEE Security Privacy , 2018
2018
Later among the works it cites.
T. Avgerinos, D. Brumley, J. Davis, R. Goulden, T. Nighswander, A. Rebert, and N. Williamson, “The mayhem cyber reasoning system,” IEEE Security Privacy , 2018
2018
Later among the works it cites.
M. Monperrus, “Automatic software repair: A bibliography,” ACM Computing Surveys , 2018
2018
Later among the works it cites.
M. Botacin, L. Galante, P. de Geus, and A. Grgio, “RevEngE is a dish served cold: Debug-Oriented Malware Decompilation and Reassembly,” in Reversing and Offensive-oriented Trends Symposium . ACM, 2019
2019
Later among the works it cites.
C. L. Goues, M. Pradel, and A. Roychoudhury, “Automated program repair,” Communications of the ACM , 2019
2019
Later among the works it cites.
Y. Hu, Y. Zhang, and D. Gu, “Automatically patching vulnerabilities of binary programs via code transfer from correct versions,” IEEE Access , 2019
2019
Later among the works it cites.
R. Duan, A. Bijlani, Y. Ji, O. Alrawi, Y. Xiong, M. Ike, B. Saltaformaggio, and W. Lee, “Automating patching of vulnerable open-source software versions in application binaries,” in Network and Distributed System Security Symposium . Internet Society, 2019
2019
Later among the works it cites.
A. Maier, H. Gascon, C. Wressnegger, and K. Rieck, “TypeMiner: Recovering Types in Binary Programs Using Machine Learning,” in Int. Conf. on Detection of Intrusions and Malware, and Vulnerability Assessment , 2019
2019
Later among the works it cites.
Z. Liu and S. Wang, “How far we have come: testing decompilation correctness of C decompilers,” in Int. Symp. on Software Testing and Analysis . ACM, 2020
2020
Later among the works it cites.
A. Gussoni, A. Di Federico, P. Fezzardi, and G. Agosta, “A comb for decompiled c code,” in ACM Asia Conference on Computer and Communications Security . ACM, 2020
2020
Later among the works it cites.
T. Hirsch, “A fault localization and debugging support framework driven by bug tracking data,” in Int. Symp. on Software Reliability Engineering Workshops (ISSREW) . IEEE, 2020
2020
Later among the works it cites.
M. Motwani and Y. Brun, “Automatically repairing programs using both tests and bug reports,” arXiv preprint arXiv:2011.08340 , 2020
Original
2020
Later among the works it cites.
D. Williams-King, H. Kobayashi, K. Williams-King, G. Patterson, F. Spano, Y. J. Wu, J. Yang, and V. P. Kemerlis, “Egalito: Layout-agnostic binary recompilation,” in Architectural Support for Programming Languages and Operating Systems (ASPLOS) , 2020
2020
Later among the works it cites.
A. Flores-Montoya and E. Schulte, “Datalog disassembly,” in USENIX , 2020
2020
Later among the works it cites.
G. J. Duck, X. Gao, and A. Roychoudhury, “Binary rewriting without control flow recovery,” in Programming Language Design and Implementation . ACM, 2020
2020
Later among the works it cites.
T. Lutellier, H. V. Pham, L. Pang, Y. Li, M. Wei, and L. Tan, “Coconut: combining context-aware neural translation models using ensemble for program repair,” 2020
2020
Later among the works it cites.
N. Harrand, C. Soto-Valero, M. Monperrus, and B. Baudry, “Java decompiler diversity and its application to meta-decompilation,” Journal of Systems and Software , 2020
2020
Later among the works it cites.
trailofbits, “trailofbits/cb-multios: Darpa challenges sets for linux, windows, and macos,” https://github.com/trailofbits/cb-multios , 2017, accessed: 2021-08-07
2021
Later among the works it cites.
“Podofo download — sourceforge.net,” https://sourceforge.net/projects/podofo/ , accessed: 2021-07-28
2021
Later among the works it cites.
“Matthias-wandel/jhead,” https://github.com/Matthias-Wandel/jhead , accessed: 2021-07-28
2021
Later among the works it cites.
“Rode0day,” https://rode0day.mit.edu/ , accessed: 2022-07-20
2022
Closest in time.
H. Ye, M. Martinez, and M. Monperrus, “Neural program repair with execution-based backpropagation,” in Proceedings of the 44th International Conference on Software Engineering , 2022
2022
Closest in time.
M. Fu, C. Tantithamthavorn, T. Le, V. Nguyen, and D. Phung, “Vulrepair: a t5-based automated software vulnerability repair,” in Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering , 2022
2022
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…