ESfix: An Embedded Program Repair Tool for Effective Removal of Concurrency Defects
Abstract
:1. Introduction
- We proposed new repair framework called ESfix, which aims to repair concurrency defects in embedded programs.
- We optimize the interrupt disable/enable strategy and the locking strategy to reduce the performance overhead.
- We optimize the reordering strategy and proposed a semantic analysis method to avoid introducing new bugs.
- We evaluate ESfix in the context of detector-reported bugs, and ESfix automatically repairs most real-world concurrency defect bugs (92.6%) with performance and simplicity similar to manual verification.
2. Background and Motivation
2.1. Example Program
2.2. Challenges
3. Method
3.1. Overall Framework
3.2. Interrupt Disable/Enable Strategy
- Static analysis: identify the access points of the shared variables s_sec and s_mils and confirm that they are located in a non-atomic operation region.
- Interrupt operation insertion:Insert before access (disable isr1 interrupt before line 4).Insert after access (enable isr1 interrupt after line 5).
- Deadlock avoidance: verifying that there is no overlap of mutually exclusive resources between insertion locations and through Equation (1) to ensure that no task blocking is caused by interrupt disabling.
3.3. Lock Selection Strategy
Algorithm 1 Lock strategy selection algorithm |
Input: Data race pairwise sets C, Output: Repair strategy
|
- For a data race pair , the lock for the rest of the thread where is located is the same as the lock protecting in the other thread. We can extend the lock scope of the thread, in which is located to include the operation by extending its scope.
- For a data race pair , there is an overlap of the critical regions protected by locks in and , and there are no other instructions in the critical regions. We can merge the critical regions and replace both locks using the same lock to reduce the number of repair operations.
Algorithm 2 Inferring new locks from bug sets |
Input: Bug Set P, Output: newly added lock
|
3.4. Reordering Strategy
4. Experiments
- RQ1: How does ESfix compare to other repair tools in terms of effectiveness and performance of atomicity violation repair?
- RQ2: How does ESfix perform in repairing the data race on industrial embedded projects?
4.1. Experimental Setup
4.2. Generalized Dataset Atomicity Violation Repair Analysis
4.2.1. Repair Effectiveness
4.2.2. Repair Efficiency Comparison
4.3. Embedded Software on Atomicity Violation Repair Analysis
4.4. Data Race Repair Analysis
5. Related Work
5.1. Semantics-Driven Methods
5.2. Generation-Verification Methods
5.2.1. Search-Based
5.2.2. Template-Based
5.2.3. Learning-Based
6. Conclusions
Author Contributions
Funding
Institutional Review Board Statement
Data Availability Statement
Conflicts of Interest
References
- Chen, D.; Jiang, Y.; Xu, C.; Ma, X. On interleaving space exploration of multi-threaded programs. Front. Comput. Sci. 2021, 15, 154206. [Google Scholar] [CrossRef]
- Deng, D.; Zhang, W.; Lu, S. Efficient concurrency-bug detection across inputs. ACM Sigplan Not. 2013, 48, 785–802. [Google Scholar] [CrossRef]
- Zhang, Q.; Fang, C.; Ma, Y.; Sun, W.; Chen, Z. A survey of learning-based automated program repair. ACM Trans. Softw. Eng. Methodol. 2023, 33, 1–69. [Google Scholar] [CrossRef]
- Le Goues, C.; Pradel, M.; Roychoudhury, A. Automated program repair. Commun. ACM 2019, 62, 56–65. [Google Scholar] [CrossRef]
- Britton, T.; Jeng, L.; Carver, G.; Cheak, P.; Katzenellenbogen, T. Automated Program Repair; Technology Reports; Judge Business School, University Cambridge: Cambridge, UK, 2013; Volume 229, pp. 1–19. [Google Scholar]
- Yun, J.; Rustamov, F.; Kim, J.; Shin, Y. Fuzzing of embedded systems: A survey. ACM Comput. Surv. 2022, 55, 1–33. [Google Scholar] [CrossRef]
- Bai, J.J.; Li, T.; Hu, S.M. DLOS: Effective static detection of deadlocks in OS kernels. In Proceedings of the 2022 USENIX Annual Technical Conference (USENIX ATC 22), Carlsbad, CA, USA, 11–13 July 2022; pp. 367–382. [Google Scholar]
- Fu, H.; Wang, Z.; Chen, X.; Fan, X. A systematic survey on automated concurrency bug detection, exposing, avoidance, and fixing techniques. Softw. Qual. J. 2018, 26, 855–889. [Google Scholar] [CrossRef]
- Zhu, Q.; Sun, Z.; Xiao, Y.A.; Zhang, W.; Yuan, K.; Xiong, Y.; Zhang, L. A syntax-guided edit decoder for neural program repair. In Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, Athens, Greece, 23–28 August 2021; pp. 341–353. [Google Scholar]
- Winter, E.; Nowack, V.; Bowes, D.; Counsell, S.; Hall, T.; Haraldsson, S.; Woodward, J. Let’s talk with developers, not about developers: A review of automatic program repair research. IEEE Trans. Softw. Eng. 2022, 49, 419–436. [Google Scholar] [CrossRef]
- Xuan, J.; Martinez, M.; Demarco, F.; Clement, M.; Marcote, S.L.; Durieux, T.; Monperrus, M. Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs. IEEE Trans. Softw. Eng. 2017, 43, 34–55. [Google Scholar] [CrossRef]
- Le, X.B.D.; Chu, D.H.; Lo, D.; Le Goues, C.; Visser, W. S3: Syntax-and semantic-guided repair synthesis via programming by examples. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, Carlsbad, CA, USA, 11–13 July 2017; pp. 593–604. [Google Scholar]
- Yi, J.; Ismayilzada, E. Speeding up constraint-based program repair using a search-based technique. Inf. Softw. Technol. 2022, 146, 106865. [Google Scholar] [CrossRef]
- Villanueva, O.M.; Trujillo, L.; Hernandez, D.E. Novelty search for automatic bug repair. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, Cancún, Mexico, 8–12 July 2020; pp. 1021–1028. [Google Scholar]
- Xu, X.; Sui, Y.; Yan, H.; Xue, J. 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), Montreal, QC, Canada, 25–31 May 2019; pp. 512–523. [Google Scholar]
- Liu, K.; Koyuncu, A.; Kim, D.; Bissyandé, T.F. TBar: Revisiting template-based automated program repair. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis, Beijing, China, 15–19 July 2019; pp. 31–42. [Google Scholar]
- Xia, C.S.; Wei, Y.; Zhang, L. Automated program repair in the era of large pre-trained language models. In Proceedings of the 2023 IEEE/ACM 45th International Conference on Software Engineering (ICSE), Melbourne, Australia, 14–20 May 2023; pp. 1482–1494. [Google Scholar]
- Jin, G.; Song, L.; Zhang, W.; Lu, S.; Liblit, B. Automated atomicity-violation fixing. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, San Jose, CA, USA, 4–8 June 2011; pp. 389–400. [Google Scholar]
- Li, C.; Chen, R.; Wang, B.; Yu, T.; Gao, D.; Yang, M. Precise and efficient atomicity violation detection for interrupt-driven programs via staged path pruning. In Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis, Virtual, Republic of Korea, 18–22 July 2022; pp. 506–518. [Google Scholar]
- Wu, X.; Chen, L.; Miné, A.; Dong, W.; Wang, J. Numerical static analysis of interrupt-driven programs via sequentialization. In Proceedings of the 2015 International Conference on Embedded Software (EMSOFT), Amsterdam, The Netherlands, 4–9 October 2015; pp. 55–64. [Google Scholar]
- Mukherjee, S.; Kumar, A.; D’Souza, D. Detecting all high-level dataraces in an RTOS kernel. In Proceedings of the Verification, Model Checking, and Abstract Interpretation: 18th International Conference, VMCAI 2017, Paris, France, 15–17 January 2017; pp. 405–423. [Google Scholar]
- Li, C.; Chen, R.; Wang, B.; Wang, Z.; Yu, T.; Jiang, Y.; Yang, M. An Empirical Study on Concurrency Bugs in Interrupt-Driven Embedded Software. In Proceedings of the 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA’23), Seattle, WA, USA, 17–21 July 2023; pp. 1345–1356. [Google Scholar]
- Zhao, J.; Wu, Y.; Dong, J. Efficient data race detection for interrupt-driven programs via path feasibility analysis. J. Supercomput. 2024, 80, 21699–21725. [Google Scholar] [CrossRef]
- Zhao, J.; Fu, Y.; Wu, Y.; Dong, J.; Hong, R. Thread-sensitive fuzzing for concurrency bug detection. Comput. Secur. 2025, 148, 104171. [Google Scholar] [CrossRef]
- Yu, B.; Tian, C.; Xing, H. Detecting Atomicity Violations in Interrupt-Driven Programs via Interruption Points Selecting and Delayed ISR-Triggering. In Proceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, San Francisco, CA, USA, 3–9 December 2023; pp. 1153–1164. [Google Scholar]
- Sung, C.; Kusano, M.; Wang, C. Modular verification of interrupt-driven software. In Proceedings of the 2017 32nd IEEE/ACM International Conference on Automated Software Engineering (ASE), Urbana, IL, USA, 30 October–3 November 2017; pp. 206–216. [Google Scholar]
- Jin, G.; Zhang, W.; Deng, D. Automated Concurrency-Bug Fixing. In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12), Hollywood, CA, USA, 8–10 October 2012; pp. 221–236. [Google Scholar]
- Yu, J.; Narayanasamy, S. A case for an interleaving constrained shared-memory multi-processor. ACM SIGARCH Comput. Archit. News 2009, 37, 325–336. [Google Scholar] [CrossRef]
- Cai, Y.; Cao, L.; Zhao, J. Adaptively generating high quality fixes for atomicity violations. In Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering, Paderborn, Germany, 4–8 September 2012; pp. 303–314. [Google Scholar]
- Chen, Z.; Kommrusch, S.; Tufano, M.; Pouchet, L.N.; Poshyvanyk, D.; Monperrus, M. Sequencer: Sequence-to-sequence learning for end-to-end program repair. IEEE Trans. Softw. Eng. 2019, 47, 1943–1959. [Google Scholar] [CrossRef]
- Hua, J.; Zhang, M.; Wang, K.; Khurshid, S. Sketchfix: A tool for automated program repair approach using lazy candidate generation. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, Lake Buena Vista, FL, USA, 4–9 November 2018; pp. 888–891. [Google Scholar]
- Mechtaev, S.; Nguyen, M.D.; Noller, Y.; Grunske, L.; Roychoudhury, A. Semantic program repair using a reference implementation. In Proceedings of the 40th International Conference on Software Engineering, Gothenburg, Sweden, 27 May–3 June 2018; pp. 129–139. [Google Scholar]
- Wardat, M.; Le, W.; Rajan, H. Deeplocalize: Fault localization for deep neural networks. In Proceedings of the 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE), Madrid, Spain, 22–30 May 2021; pp. 251–262. [Google Scholar]
- Wong, W.E.; Gao, R.; Li, Y.; Abreu, R.; Wotawa, F. A survey on software fault localization. IEEE Trans. Softw. Eng. 2016, 42, 707–740. [Google Scholar] [CrossRef]
- Gazzola, L.; Micucci, D.; Mariani, L. Automatic Software Repair: A Survey. IEEE Trans. Softw. Eng. 2019, 45, 34–67. [Google Scholar] [CrossRef]
- Weimer, W.; Nguyen, T.; Le Goues, C.; Forrest, S. Automatically finding patches using genetic programming. In Proceedings of the 2009 IEEE 31st International Conference on Software Engineering, Vancouver, BC, Canada, 16–24 May 2009; pp. 364–374. [Google Scholar]
- Kelk, D.; Jalbert, K.; Bradbury, J.S. Automatically repairing concurrency bugs with ARC. In Proceedings of the Multicore Software Engineering, Performance, and Tools: International Conference, MUSEPAT 2013, St. Petersburg, Russia, 19–20 August 2013; pp. 73–84. [Google Scholar]
- Yu, X.L.; Al-Bataineh, O.; Lo, D.; Roychoudhury, A. Smart contract repair. ACM Trans. Softw. Eng. Methodol. (TOSEM) 2020, 29, 1–32. [Google Scholar] [CrossRef]
- Zhang, Y.; Ma, S.; Li, J.; Li, K.; Nepal, S.; Gu, D. Smartshield: Automatic smart contract protection made easy. In Proceedings of the 2020 IEEE 27th International Conference on Software Analysis, Evolution and Reengineering (SANER), London, ON, Canada, 18–21 February 2020; pp. 23–34. [Google Scholar]
- Huang, R.; Shen, Q.; Wang, Y.; Wu, Y.; Wu, Z.; Luo, X.; Ruan, A. ReenRepair: Automatic and semantic equivalent repair of reentrancy in smart contracts. J. Syst. Softw. 2024, 216, 112107. [Google Scholar] [CrossRef]
- Liu, H.; Chen, Y.; Lu, S. Understanding and generating high quality patches for concurrency bugs. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, Seattle, WA, USA, 13–18 November 2016; pp. 715–726. [Google Scholar]
- Nguyen, T.D.; Pham, L.H.; Sun, J. SGUARD: Towards fixing vulnerable smart contracts automatically. In Proceedings of the 2021 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, 24–27 May 2021; pp. 1215–1229. [Google Scholar]
- Ferreira Torres, C.; Jonker, H.; State, R. Elysium: Context-aware bytecode-level patching to automatically heal vulnerable smart contracts. In Proceedings of the 25th International Symposium on Research in Attacks, Intrusions and Defenses, Limassol, Cyprus, 26–28 October 2022; pp. 115–128. [Google Scholar]
- Li, Y.; Wang, S.; Nguyen, T.N. Dear: A novel deep learning-based approach for automated program repair. In Proceedings of the 44th International Conference on Software Engineering, Pittsburgh, PA, USA, 21–29 May 2022; pp. 511–523. [Google Scholar]
- Jiang, N.; Lutellier, T.; Tan, L. Cure: Code-aware neural machine translation for automatic program repair. In Proceedings of the 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE), Madrid, Spain, 22–30 May 2021; pp. 1161–1173. [Google Scholar]
- Guo, H.; Chen, Y.; Chen, X.; Huang, Y.; Zheng, Z. Smart contract code repair recommendation based on reinforcement learning and multi-metric optimization. ACM Trans. Softw. Eng. Methodol. 2024, 33, 1–31. [Google Scholar] [CrossRef]
- Xia, C.S.; Zhang, L. Less training, more repairing please: Revisiting automated program repair via zero-shot learning. In Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering, Singapore, 14–18 November 2022; pp. 959–971. [Google Scholar]
- Xiao, J.; Xu, Z.; Chen, S.; Lei, G.; Fan, G.; Cao, Y.; Feng, Z. Confix: Combining Node-Level Fix Templates and Masked Language Model for Automatic Program Repair. J. Syst. Softw. 2024, 216, 112116. [Google Scholar] [CrossRef]
No. | Name | Describe |
---|---|---|
1 | logger | Procedure for modeling a portion of the firmware of a temperature recording device in a large industrial enterprise. |
2 | blink | Program to control LEDs connected to MSP430 hardware. |
3 | brake | Used to calculate brake torque based on the speed of each wheel. |
4 | i2c_pca_isa | Programs collected from Linux kernel drivers to support hardware ISA boards. |
5 | i8xx_tco | Programs collected from Linux kernel drivers to support TCO timers for the i8xx chipset. |
6 | wdt_pci | Programs collected from Linux kernel drivers for watchdogs. |
7 | Generalized Dataset 1 | CFix-built bug-repair benchmark suite with 6 atomicity violation benchmarks from open-source C/C++ multi-threaded applications. |
8 | Generalized Dataset 2 | The real-world benchmarks used in the previous methodology had a total of nine programs that contained atomicity violation bugs. |
No. | Name | Loc. | Describe |
---|---|---|---|
1 | mv643xx_eth | 3256 | A device driver in the Linux kernel. |
2 | short | 704 | A driver in LDD. |
3 | shortprint | 531 | A driver in LDD. |
4 | mpu401_uart | 630 | A device driver in the Linux kernel. |
5 | module1 | 168 | A Lower Disk Driver. |
6 | module2 | 154 | An engine power control software. |
7 | module3 | 99 | A thermal control software. |
8 | module4 | 1710 | A power control software. |
9 | module5 | 2273 | CA battery supply control software. |
Program | Atomicity Violation Repair Rate | Average Expenditure | ||||
---|---|---|---|---|---|---|
15 | 35.6%(11) | 69.2%(14) | 92.6%(14) | 85.9% | 29.4% | 11.8% |
Name. | Size(Loc) | #B | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
#C | #D | Fix Date | #C | #D | Fix Date | #C | #D | Fix Date | |||||
Apache-25520 | 333K | 6 | 2 | 1 | 33.3% | 5 | 0 | 83.3% | 6 | 0 | 100.0% | ||
MySQL-791 | 125 | 2 | 0 | 0 | 0.0% | 1 | 0 | 50.0% | 2 | 0 | 100.0% | ||
MySQL-3596 | 122 | 4 | 1 | 0 | 25.0% | 4 | 0 | 100.0% | 4 | 0 | 100.0% | ||
Mozilla-142651 | 87K | 1 | 0 | 1 | 0.0% | 0 | 1 | 0.0% | 0 | 0 | 0.0% | ||
Cherokee-326 | 83K | 5 | 3 | 1 | 60.0% | 4 | 1 | 80.0% | 5 | 0 | 100.0% | ||
Mozilla-18025 | 108K | 2 | 0 | 1 | 0.0% | 2 | 1 | 100.0% | 2 | 0 | 100.0% | ||
Aget-0.4 | 320 | 2 | 1 | 0 | 50.0% | 1 | 0 | 50.0% | 2 | 0 | 100.0% | ||
Apache-21285 | 45.34K | 9 | 4 | 1 | 44.4% | 7 | 0 | 77.8% | 8 | 0 | 88.9% | ||
Apache-21287 | 45.61K | 7 | 3 | 0 | 42.9% | 4 | 0 | 57.1% | 7 | 0 | 100.0% | ||
Memcached-127 | 1.27K | 5 | 1 | 0 | 20.0% | 2 | 0 | 40.0% | 5 | 0 | 100.0% | ||
MySQL-12228 | 122 | 4 | 1 | 1 | 25.0% | 2 | 0 | 50.0% | 4 | 0 | 100.0% | ||
MySQL-12848 | 181 | 2 | 2 | 1 | 100.0% | 2 | 0 | 100.0% | 2 | 0 | 100.0% | ||
MySQL-169 | 145 | 4 | 0 | 0 | 0.0% | 4 | 0 | 100.0% | 4 | 0 | 100.0% | ||
MySQL-2011 | 126 | 6 | 2 | 0 | 33.3% | 3 | 0 | 50.0% | 6 | 0 | 100.0% | ||
MySQL-644 | 118 | 1 | 1 | 0 | 100.0% | 1 | 0 | 100.0% | 2 | 0 | 100.0% | ||
SUM | 60 | 21 | 7 | 35.6% | 42 | 3 | 69.2% | 58 | 0 | 92.6% |
Name | #LOC | #SV | #Race | #C | #F | #D | Repair Rate |
---|---|---|---|---|---|---|---|
logger | 578 | 46 | 21 | 19 | 2 | 0 | 90.5% |
blink | 373 | 57 | 26 | 25 | 2 | 1 | 96.2% |
brake | 1975 | 130 | 7 | 7 | 2 | 0 | 100.0% |
i2c_pca_isa | 1063 | 20 | 20 | 18 | 2 | 0 | 90.0% |
i8xx_tco | 2671 | 60 | 2 | 2 | 0 | 0 | 100.0% |
wdt_pci | 3513 | 61 | 21 | 18 | 3 | 0 | 85.75% |
No. | Name | #Race | Strategy | #D | Repair Status | Time (s) |
---|---|---|---|---|---|---|
1 | mv643xx_eth | 10 | 0 | success | 54.62 | |
2 | short | 18 | 0 | success | 16.07 | |
3 | shortprint | 0 | N/A | N/A | success | N/A |
4 | mpu401_uart | 47 | 0 | success | 108.75 | |
5 | module1 | 4 | 0 | success | 5.93 | |
6 | module2 | 64 | 0 | success | 13.43 | |
7 | module3 | 12 | 0 | success | 9.87 | |
8 | module4 | 9 | 0 | success | 21.40 | |
9 | module5 | 13 | 0 | success | 58.92 |
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content. |
© 2025 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).
Share and Cite
Zhao, J.; Wu, Y.; Fu, Y.; Liu, S. ESfix: An Embedded Program Repair Tool for Effective Removal of Concurrency Defects. Entropy 2025, 27, 294. https://doi.org/10.3390/e27030294
Zhao J, Wu Y, Fu Y, Liu S. ESfix: An Embedded Program Repair Tool for Effective Removal of Concurrency Defects. Entropy. 2025; 27(3):294. https://doi.org/10.3390/e27030294
Chicago/Turabian StyleZhao, Jingwen, Yanxia Wu, Yan Fu, and Shuyong Liu. 2025. "ESfix: An Embedded Program Repair Tool for Effective Removal of Concurrency Defects" Entropy 27, no. 3: 294. https://doi.org/10.3390/e27030294
APA StyleZhao, J., Wu, Y., Fu, Y., & Liu, S. (2025). ESfix: An Embedded Program Repair Tool for Effective Removal of Concurrency Defects. Entropy, 27(3), 294. https://doi.org/10.3390/e27030294