Constructing a Complex for Automated Debugging of Fragmented Programs

The paper is devoted to the authors’ tools for automated debugging of fragmented programs in the LuNA (Language for Numerical Algorithms) system. The LuNA system uses approach of fragmented programming, which allows the researcher to design parallel programs in an automated mode.

The main problem discussed in the paper is the detection of errors specific to LuNA programs. The operation algorithms of four developed tools for automated debugging of LuNA programs are described. Three of them are based on the static analysis approach and differ in the intermediate representations used. The first uses an abstract syntax tree (AST). The second uses a data dependency graph (DDG). The third tool generates a Prolog program containing a set of facts about the original LuNA program and rules corresponding to erroneous situations. Due to the use of various intermediate representations, each of the static analysis tools is able to detect its own types of errors. The last tool uses the “post-mortem analysis” approach. Each process of a parallel program collects a trace file during its operation and at the end of the work these files are analyzed by a special utility.

The paper also describes the developed utility for testing automated debugging tools. The set of test programs with various errors, as well as error-free programs, has been developed  for this utility.

The last part describes the designed mechanism for integrating the developed automated debugging tools into a single software package.

1. Malyshkin V., Perepelkin V., Lyamin A. Trace Balancing Technique for Trace Playback in LuNA System. In: Malyshkin, V. (eds) Parallel Computing Technologies. PaCT 2023. Lecture Notes in Computer Science, 2023, vol. 14098. Springer, Cham., pp. 42–50. DOI: 10.1007/978-3-031-41673-6_4.

2. Malyshkin V. E. Technology of fragmented programming. Vestnik YuUrGU. Series: Computational Mathematics and Software Engineering, 2012, no. 46 (305), pp. 45–55 (in Russ.). DOI: 10.14529/cmse120104

3. Zubov M. V., Pustygin A. N., Starcev E. V. The use of universal intermediate representations for static analysis of the source code. Reports of Tomsk State University of Control Systems and Radioelectronics, 2013, no. 1(27), pp. 64–68.

4. Flederer F., Ostermayer L., Seipel D., Montenegro S. Source Code Verifi cation for Embedded Systems using Prolog. Electronic Proceedings in Theoretical Computer Science, 2016, vol. 234, pp. 88–103. DOI: 10.4204/EPTCS.234.7

5. Abramson D. A., Watson G., Le P. D. Guard: a tool for migrating scientifi c applications to the .NET Framework. In P. M. A. Sloot, C. J. K. Tan, J. J. Dongarra, & A. G. Hoekstra (Eds.) Computational Science – ICCS 2002: International Conference Amsterdam, The Netherlands, April 21–24, 2002 Proceedings, pp. 834843. (Lecture Notes in Computer Science; Vol. 2330). Springer. DOI: 10.1007/3-540-46080-2_88

6. Bakhtin V. A., Kataev N. A., Kolganov A. S., Yakobovskiy M. V., Zaharov D. A. Automation of programming for promising high-performance computing systems. In: Malyshkin V. (eds) Parallel Computing Technologies. PaCT 2023. Lecture Notes in Computer Science, Cham: Springer, 2023, vol. 14098, pp. 3–17.

7. Malyshkin V., Vlasenko A., Michurov M. Automated Debugging of Fragmented Programs in LuNA System. Proc. of Mathematical Modeling and Supercomputer Technologies 2022. Communications in Computer and Information Science, 2022, vol. 1750, pp. 266–280. DOI: 10.1007/978-3-031-24145-1_22

8. Protze J., Hilbrich T., Schulz M., de Supinski B. R. MPI Runtime Error Detection with MUST: A Scalable and Crash-Safe Approach. Proc. of 43rd International Conference on Parallel Processing Workshops. Minneapolis, MN, USA, 2014, p. 206–215. DOI: 10.1109/ICPPW.2014.37

9. Karpov J. G. MODEL CHECKING. Verifi cation of parallel and distributed software systems. Saint Petersburg, BHV-Peterburg publ., 2010, 560 p. (in Russ.)

10. Holzmann G. J., Joshi R. Model-Driven Software Verifi cation. In: Graf S., Mounier, L. (eds) Model Checking Software. Proc. of SPIN 2004. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 2004, vol. 2989, p. 7691. DOI: 10.1007/978-3-540-24732-6_6

11. Fokkink W. Distributed Algorithms, second edition: An Intuitive Approach. MIT Press, 2018, 272 p.

12. Kas’janov V. N., Evstigneev V. A. Graphs in programming: processing, visualization and application. Saint Petersburg, BHV-Peterburg publ., 2003, 1104 p. (in Russ.)

13. Belevancev A. A. Multilevel static analysis of the source code to ensure the quality of programs. Programming and Computer Software, 2017, vol. 43, no. 6, p. 325. (in Russ.)

14. Krinke J. Information Flow Control and Taint Analysis with Dependence Graphs. Vancouver: Proc. of 3d International Workshop on Code Based Software Security Assessments (CoBaSSA), 2007, p. 69.

15. Kuck D. J., Kuhn R. H., Padua D. A., Leasure B., Wolfe M. Dependence graphs and compiler optimizations. Proc. of the 8th ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages (POPL), 1981, p. 207218. DOI: 10.1145/567532.567555

16. Smaragdakis Y., Bravenboer M. Using Datalog for Fast and Easy Program Analysis. In: de Moor O., Gottlob G., Furche T., Sellers A. (eds) Datalog Reloaded. Lecture Notes in Computer Science.. Springer, Berlin, Heidelberg, 2010, vol. 6702, p. 245251. DOI: 10.1007/978-3-642-24206-9_14