access icon free Program analysis too loopy? Set the loops aside

© The Institution of Engineering and Technology
Received 29/03/2012, Accepted 13/01/2013, Revised 12/12/2012, Published

Among the many obstacles to efficient and sound program analysis, loops may be the most prevalent. In program analyses that traverse paths, loops introduce a variable, possibly infinite and number of paths. This study assesses the potential of a program analysis technique that analyses loops separately and replaces the loop with a summary, similar to how many analyses use summaries for interprocedural analysis. This study is conducted by comparing the path counts when loops are analysed separately to a baseline path count where loops are traversed at most once. Although the number of paths is decreased in many cases, the magnitude of the decrease is typically not sufficient for long, complex functions. In addition, loops are classified by the task they perform, analysed using the number of paths as an estimate of their complexity and further inspected for programming elements that may make loop analysis more difficult. Of the 2869 loops used in this study, 84% of the loops have fewer than ten paths and only 1.3% have more than 10 000 paths. Nearly 60% of the loops traverse arrays or strings and roughly half of the loops contain a function call.

Inspec keywords: program diagnostics; program control structures

Other keywords: interprocedural analysis; loop traverse strings; function call; programming elements; baseline path count; loop traverse arrays; complex functions; program analysis technique; loop analysis

Subjects: Systems analysis and programming; Diagnostic, testing, debugging and evaluating systems; Compilers, interpreters and other processors

References

    1. 1)
      • 32. McCabe, T.: ‘A complexity measure’, IEEE Trans. Softw. Eng., 1976, SE-2, (4), pp. 308–320 (doi: 10.1109/TSE.1976.233837).
    2. 2)
      • 25. Tillmann, N., de Halleux, J.: ‘Pex–white box test generation for .NET’, Tests Proofs, Lecture Notes Comput. Sci., 2008, 4966, pp. 134–153 (doi: 10.1007/978-3-540-79124-9_10).
    3. 3)
      • 11. Flanagan, C., Qadeer, S.: ‘Predicate abstraction for software verification’. Proc. Symp. Principles of Programming Languages, Portland, Oregon, 2002, pp. 191–202.
    4. 4)
      • 20. Zhao, Y., Gong, Y., Liu, L., Xiao, Q., Yang, Z.: ‘Context-sensitive interprocedural defect detection based on a unified symbolic procedure summary model’. Proc. 11th Int. Conf. Quality Software, Madrid, Spain, 2011, pp. 51–60.
    5. 5)
      • 12. Lokuciejewski, P., Cordes, D., Falk, H., Marwedel, P.: ‘A fast and precise static loop analysis based on abstract interpretation, program slicing and polytope models’. Proc. Int. Symp. Code Generation and Optimization, Seattle, Washington, 2009, pp. 136–146.
    6. 6)
      • 30. Dillig, I., Dillig, T., Aiken, A.: ‘Sound, complete and scalable path-sensitive analysis’. Proc. Conf. Programming Language Design and Implementation, Tucson, Arizona, 2008, pp. 270–280.
    7. 7)
      • 16. Xie, Y., Chou, A., Engler, D.: ‘ARCHER: using symbolic, path-sensitive analysis to detect memory access errors’. Proc. Ninth European Software Engineering Conf. held jointly with 11th ACM SIGSOFT Int. Symp. Foundations of Software Engineering, Helsinki, Finland, 2003, pp. 327–336.
    8. 8)
      • 15. White, L., Wiszniewski, B.: ‘Path testing of computer programs with loops using a tool for simple loop patterns’, Softw., Pract. Exp., 1991, 21, (10), pp. 1075–1102 (doi: 10.1002/spe.4380211007).
    9. 9)
      • 24. Sen, K., Marinov, D., Agha, G.: ‘CUTE: a concolic unit testing engine for C’. Proc. 10th European Software Engineering Conf. held jointly with 13th ACM SIGSOFT Int. Symp. Foundations of Software Engineering, Lisbon, Portugal, 2005, pp. 263–272.
    10. 10)
      • 21. Yorsh, G., Yahav, E., Chandra, S.: ‘Generating precise and concise procedure summaries’. Proc. 35th Annual Symp. Principles of Programming Languages, San Francisco, California, 2008, pp. 221–234.
    11. 11)
      • 7. GrammaTech, Inc.: ‘CodeSurfer’ http://www.grammatech.com/products/codesurfer/overview.html, accessed March 2012.
    12. 12)
      • 13. Kirner, M.: ‘Automatic loop bound analysis of programs written in C’. Master's thesis, Technischen Universitat at Wien, 2006.
    13. 13)
      • 29. Das, M., Lerner, S., Seigle, M.: ‘ESP: path-sensitive program verification in polynomial time’. Proc. Conf. Programming Language Design and Implementation, Berlin, Germany, 2002, pp. 57–68.
    14. 14)
      • 28. Harman, M., Hierons, R., Danicic, S., Howroyd, J., Laurence, M., Fox, C.: ‘Node coarsening calculi for program slicing’. Proc. Eighth Working Conf. Reverse Engineering, Stuttgart, Germany, 2001, pp. 25–34.
    15. 15)
      • 14. Burnim, J., Jalbert, N., Stergiou, C., Sen, K.: ‘Looper: lightweight detection of infinite loops at runtime’. Proc. IEEE/ACM Int. Conf. Automated Software Engineering, Auckland, New Zealand, 2009, pp. 161–169.
    16. 16)
      • 23. Saxena, P., Poosankam, P., McCamant, S., Song, D.: ‘Loop-extended symbolic execution on binary programs’. Proc. Int. Symp. Software Testing and Analysis, Chicago, Illinois, 2009, pp. 225–236.
    17. 17)
      • 6. Kroening, D., Sharygina, N., Tonetta, S., Tsitovich, A., Wintersteiger, C.: ‘Loop summarization using abstract transformers’. Proc. Sixth Int. Symp. Automated Technology for Verification and Analysis, Seoul, Korea, 2008, pp. 111–125.
    18. 18)
      • 5. Abd-El-Hafiz, S., Basili, V.: ‘A knowledge-based approach to the analysis of loops’, IEEE Trans. Softw. Eng., 1996, 22, (5), pp. 339–360 (doi: 10.1109/32.502226).
    19. 19)
      • 27. Gabel, M., Su, Z.: ‘A study of the uniqueness of source code’. Proc. 18th ACM SIGSOFT Int. Symp. Foundations of Software Engineering, Santa Fe, New Mexico, 2010, pp. 147–156.
    20. 20)
      • 4. Godefroid, P., Luchaup, D.: ‘Automatic partial loop summarization in dynamic test generation’. Proc. 2011 Int. Symp. Software Testing and Analysis, Toronto, Canada, 2011, pp. 23–33.
    21. 21)
      • 31. Ball, T., Larus, J.: ‘Efficient path profiling’. Proc. 29th Annual ACM/IEEE Int. Symp. Microarchitecture, Paris, France, 1996, pp. 46–57.
    22. 22)
      • 19. Binkley, D., Harman, M., Lakhotia, K.: ‘FlagRemover: a testability transformation for transforming loop-assigned flags’, ACM Trans. Softw. Eng. Methodol., 2011, 20, (3), pp. 1–33 (doi: 10.1145/2000791.2000796).
    23. 23)
      • 3. Pǎsǎreanu, C., Mehlitz, P., Bushnell, D., et al: ‘Combining unit-level symbolic execution and system-level concrete execution for testing NASA software’. Proc. Int. Symp. Software Testing and Analysis, Seattle, Washington, 2008, pp. 15–26.
    24. 24)
      • 10. Martel, M.: ‘Improving the static analysis of loops by dynamic partitioning techniques’. Proc. Third Int. Workshop on Source Code Analysis and Manipulation, Amsterdam, The Netherlands, 2003, pp. 13–21.
    25. 25)
      • 34. Scientific Toolworks, Inc: ‘Understand source code analysis & metrics’. http://scitools.com/index.php, accessed March 2012.
    26. 26)
      • 8. Halstead, M.: ‘Elements of software science’ (Elsevier Science Inc., 1977).
    27. 27)
      • 18. Ngo, M., Tan, H.: ‘Detecting large number of infeasible paths through recognizing their patterns’. Proc. Sixth Joint Meeting of the European Software Engineering Conf. and the ACM SIGSOFT Symp. Foundations of Software Engineering, Dubrovnik, Croatia, 2007, pp. 215–224.
    28. 28)
      • 17. Hu, L., Harman, M., Hierons, R., Binkley, D.: ‘Loop squashing transformations for amorphous slicing’. Proc. 11th Working Conf. Reverse Engineering, Delft, The Netherlands, 2004, pp. 152–160.
    29. 29)
      • 9. Kovács, L., Voronkov, A.: ‘Finding loop invariants for programs over arrays using a theorem prover’. Proc. 12th Int. Conf. Fundamental Approaches to Software Engineering, York, UK, 2009, pp. 470–485.
    30. 30)
      • 26. Larson, E.: ‘A plethora of paths’. Proc. IEEE 17th Int. Conf. Program Comprehension, Vancouver, Canada, 2009, pp. 40–49.
    31. 31)
      • 1. King, J.: ‘Symbolic execution and program testing’, Commun. ACM, 1976, 19, (7), pp. 385–394 (doi: 10.1145/360248.360252).
    32. 32)
      • 35. Gulwani, S., Tiwari, A.: ‘Computing procedure summaries for interprocedural analysis’. Proc. European Symp. Programming, Braga, Portugal, 2007, pp. 253–267.
    33. 33)
      • 22. Ancourt, C., Coelho, F., Irigoin, F.: ‘A modular static analysis approach to affine loop invariants detection’, Electron. Notes Theor. Comput. Sci., 2010, 267, (1), pp. 3–16 (doi: 10.1016/j.entcs.2010.09.002).
    34. 34)
      • 2. Bush, W., Pincus, J., Sielaff, D.: ‘A static analyzer for finding dynamic programming errors’, Softw., Pract. Exp., 2000, 30, (7), pp. 775–802 (doi: 10.1002/(SICI)1097-024X(200006)30:7<775::AID-SPE309>3.0.CO;2-H).
    35. 35)
      • 33. Henry, S., Kafura, D., Harris, K.: ‘On the relationships among three software metrics’, ACM SIGMETRICS Perform. Eval. Rev., 1981, 10, (1), pp. 81–88 (doi: 10.1145/1010627.807911).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-sen.2012.0048
Loading

Related content

content/journals/10.1049/iet-sen.2012.0048
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading