[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1882291.1882319acmconferencesArticle/Chapter ViewAbstractPublication PagesfseConference Proceedingsconference-collections
research-article

Golden implementation driven software debugging

Published: 07 November 2010 Publication History

Abstract

The presence of a functionally correct golden implementation has a significant advantage in the software development life cycle. Such a golden implementation is exploited for software development in several domains, including embedded software --- a low resource-consuming version of the golden implementation. The golden implementation gives the functionality that the program is supposed to implement, and is used as a guide during the software development process. In this paper, we investigate the possibility of using the golden implementation as a reference model in software debugging. We perform a substantial case study involving the Busybox embedded Linux utilities while treating the GNU Core Utilities as the golden or reference implementation. Our debugging method consists of dynamic slicing with respect to the observable error in both the implementations (the golden implementation as well as the buggy software). During dynamic slicing we also perform a step-by-step weakest precondition computation of the observable error with respect to the statements in the dynamic slice. The formulae computed as weakest pre-condition in the two implementations are then compared to accurately locate the root cause of a given observable error. Experimental results obtained from Busybox suggest that our method performs well in practice and is able to pinpoint all the bugs recently published in [8] that could be reproduced on Busybox version 1.4.2. The bug report produced by our approach is concise and pinpoints the program locations inside the Busybox source that contribute to the difference in behavior.

References

[1]
Apache webserver. http://httpd.apache.org/.
[2]
Busybox. http://busybox.net/.
[3]
ERESI: the ERESI reverse engineering software interface. http://www.eresi-project.org.
[4]
libPNG library. http://www.libpng.org.
[5]
Miniweb webserver. http://miniweb.sourceforge.net/.
[6]
QEMU emulator. http://www.qemu.org.
[7]
Vine. http://bitblaze.cs.berkeley.edu/vine.html.
[8]
C. Cadar, D. Dunbar, and D. Engler. Klee: Unassisted and automatic generation of high-coverage tests for complex systems programs. In OSDI, 2009.
[9]
J. Clause and A. Orso. Penumbra: Automatically identifying failure-relevant inputs using dynamic tainting. In ISSTA, 2009.
[10]
C. Csallner and Y. Smaragdakis. DSD-Crasher: a hybrid analysis tool for bug finding. In ISSTA, 2006.
[11]
R. Cytron et al. Efficiently computing static single assignment form and the control dependence graph. ACM Trans. Program. Lang. Syst., 13(4), 1991.
[12]
V. Ganesh and D. Dill. A decision procedure for bit-vectors and arrays. In CAV, 2007.
[13]
P. Godefroid, N. Klarlund, and K. Sen. DART: Directed automated random testing. In ESEC-FSE, 2005.
[14]
B. Gulavani, T. Henzinger, Y. Kannan, A. Nori, and S. Rajamani. SYNERGY: A new algorithm for property checking. In FSE, 2006.
[15]
B. Korel and J. W. Laski. Dynamic program slicing. Information Processing Letters, 29(3):155--163, 1988.
[16]
T. Lengauer and R. Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst., 1(1):121--141, 1979.
[17]
D. Qi, A. Roychoudhury, and Z. Liang. Test generation to expose changes in evolving programs. In ASE, 2010.
[18]
D. Qi, A. Roychoudhury, Z. Liang, and K. Vaswani. DARWIN: An approach for debugging evolving programs. In ESEC-FSE, 2009.
[19]
R. Santelices, P. Chittimalli, T. Apiwattanapong, A. Orso, and M. Harrold. Test-suite augmentation for evolving software. In ASE, 2008.
[20]
D. Song et al. Bitblaze: A new approach to computer security via binary analysis. In ICISS (Keynote), 2008. http://bitblaze.cs.berkeley.edu.
[21]
A. Zeller. Yesterday my program worked, today it does not. Why? In ESEC-FSE, 1999.

Cited By

View all
  • (2021)Explaining Regressions via Alignment Slicing and MendingIEEE Transactions on Software Engineering10.1109/TSE.2019.294956847:11(2421-2437)Online publication date: 1-Nov-2021
  • (2020)A Methodology for Root-Causing In-field Attacks on Microfluidic ExecutionsTransactions on Computational Science XXXV10.1007/978-3-662-61092-3_7(119-152)Online publication date: 18-Feb-2020
  • (2019)Intent-Preserving Test Repair2019 12th IEEE Conference on Software Testing, Validation and Verification (ICST)10.1109/ICST.2019.00030(217-227)Online publication date: Apr-2019
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
FSE '10: Proceedings of the eighteenth ACM SIGSOFT international symposium on Foundations of software engineering
November 2010
302 pages
ISBN:9781605587912
DOI:10.1145/1882291
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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 November 2010

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. embedded linux
  2. software evolution
  3. symbolic execution

Qualifiers

  • Research-article

Conference

SIGSOFT/FSE'10
Sponsor:

Acceptance Rates

Overall Acceptance Rate 17 of 128 submissions, 13%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)10
  • Downloads (Last 6 weeks)0
Reflects downloads up to 24 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2021)Explaining Regressions via Alignment Slicing and MendingIEEE Transactions on Software Engineering10.1109/TSE.2019.294956847:11(2421-2437)Online publication date: 1-Nov-2021
  • (2020)A Methodology for Root-Causing In-field Attacks on Microfluidic ExecutionsTransactions on Computational Science XXXV10.1007/978-3-662-61092-3_7(119-152)Online publication date: 18-Feb-2020
  • (2019)Intent-Preserving Test Repair2019 12th IEEE Conference on Software Testing, Validation and Verification (ICST)10.1109/ICST.2019.00030(217-227)Online publication date: Apr-2019
  • (2019)Debugging Errors in Microfluidic ExecutionsAdvanced Computing and Systems for Security10.1007/978-981-13-8969-6_9(143-158)Online publication date: 29-Aug-2019
  • (2017)Dependence Guided Symbolic ExecutionIEEE Transactions on Software Engineering10.1109/TSE.2016.258406343:3(252-271)Online publication date: 1-Mar-2017
  • (2016)Apex: automatic programming assignment error explanationACM SIGPLAN Notices10.1145/3022671.298403151:10(311-327)Online publication date: 19-Oct-2016
  • (2016)Apex: automatic programming assignment error explanationProceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications10.1145/2983990.2984031(311-327)Online publication date: 19-Oct-2016
  • (2016)Formula-based software debuggingCommunications of the ACM10.1145/285610359:7(68-77)Online publication date: 24-Jun-2016
  • (2016)A new approach for root-causing attacks on digital microfluidic devices2016 IEEE Asian Hardware-Oriented Security and Trust (AsianHOST)10.1109/AsianHOST.2016.7835550(1-6)Online publication date: Dec-2016
  • (2015)relifixProceedings of the 37th International Conference on Software Engineering - Volume 110.5555/2818754.2818813(471-482)Online publication date: 16-May-2015
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media