Applications of Synchronization CoverageArkady BronIBM Haifa Research Lab,Mount Carmel,Haifa 31905, [email protected] FarchiIBM Haifa Research Lab,Mount Carmel,Haifa 31905, [email protected] MagidIBM Haifa Research Lab,Mount Carmel,Haifa 31905, [email protected] NirIBM Haifa Research Lab,Mount Carmel,Haifa 31905, [email protected] UrIBM Haifa Research Lab,Mount Carmel,Haifa 31905, [email protected] analysis is a useful testing technology. However,some coverage mo dels are more acceptable to the industrythan others. In the field of testing multi-threaded appli-cations, there is a need for a coverage model that can beused to evaluate tests for concurrent completeness and tofind new testing requirements. We present a new coveragemo del: synchronization coverage. This model is simple tounderstand and the action items generated by each uncov-ered task are clear to testers and developers . We proposethat synchronization coverage could, and should, b ecomeone of the more commonly used coverage models.Categories and Subject DescriptorsD.2.5 [SOFTWARE ENGINEERING]: Testing and De-bugging—Testing tools (e.g., data generators, coverage test-ing)General TermsAlgorithms, Measurement, Reliability, Experimentation, The-ory, VerificationKeywordsMulti-threading, coverage, testing1. INTRODUCTIONCoverage analysis is a common technique used both toevaluate the quality of testing done and to find areas ofthe code that need additional testing. No coverage measurededicated to concurrent aspects of applications has becomeaccepted practice in the industry.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.PPoPP’05, June 15–17, 2005, Chicago, Illinois, USA.Copyright 2005 ACM 1-59593-080-9/05/0006 ...$5.00.In this paper, we first discuss the requirements that acoverage model needs to fulfill to gain acceptance in theindustry. We then present a coverage model in detail: syn-chronization coverage. This model is dedicated to concur-rent aspects of programs that fulfill these requirements. Ithas gained acceptance in IBM and is now being presentedoutside IBM. We demonstrate several projects in which itwas used in different roles and explain the advantage of eachrole.This paper is organized as follows: in the second section,we explain basic coverage terms, as well as why coverageis used and for what it is us eful. In the third section, wepresent our insights about what makes some coverage mod-els superior, in practice, to others. In the fourth section, wepresent synchronization coverage. In the fifth section, wereport on the use of synchronization coverage in the field.2. BACKGROUND ON COVERAGETesting is one of the biggest problems of the software in-dustry. The cost of testing is usually between 40 and 80%of the development process, as compared with the codingitself which may be less than 20%[3]. The main techniquefor demonstrating that testing has been thorough is calledtest coverage analysis [13]. Simply stated, the idea is tocreate, in a systematic fashion, a large and comprehensivelist of tasks and check that each task is covered in the test-ing phase. Coverage can help in monitoring the quality oftesting, in creating tests for areas that have not been testedbefore, and with forming small yet comprehensive regressionsuites [4]. In this section, we discuss coverage and how it isused in the industry.Coverage is defined as any metric of completeness withrespect to a test selection criterion [2]. Many such metricshave been suggested in the past [2], of which statement cov-erage is the most common. Complete statement coveragemeans that every statement in the program has been exe-cuted by some tests. Coverage is one of the more systematicways to check that testing has been thorough. When usingany coverage model, of which many are available [11], a met-ric is created against which the quality and completeness ofthe testing is measured.The most commonly used coverage metrics are based onthe control flow of the program, such as statement coverage206and branch coverage; however, many other metrics exist.Some coverage metrics are based on the data flow of vari-ables, like de fine-use [2], while others are not based on theprogram code but on the inputs or the specifications.Coverage is usually used to find new testing requirementsthat were overlooked in the test plan. Often the test require-ments are written during the design and do not take into ac-count the details of the implementation. For example, theimplementation of a sorting function might use two differentalgorithms, depending on the size of the array sorted, a de-tail which is not in the specifications. In this case, statementcoverage might show that the inputs never included the caseof a short array that uses one of the algorithms, and thata new test is needed. Working with coverage as a guide toimprove the quality of testing has been shown to be a costeffective use of resources [16].Another application of coverage that is commonly usedis the generation of regression suites [13]. The generationof regression suites has two contradictory requirements: thesuite must be small enough to be economical to execute afterevery design change, yet it must be comprehensive enough tofind the bugs that were introduced. Using cove rage one canfind a relatively small set of tests, which is comprehensivein the sense that it covers the required metric [4].A number of standards, as well as internal company poli-cies, require that the testing program achieves some levelof coverage, under some model. For example, one of therequirements of the DOA standard [1] is 100% statementcoverage.There are many coverage tools that support all major pro-gramming languages. Each tool implements a number ofcoverage models for a particular combination of operatingsystem, compiler, and programming language. Most of themwork by instrumenting the source code and adding countersthat can later be used by the tool’s user interface to showthe coverage status and progress in some detail. To applysuch a tool, one typically has to recompile the software withthe tool and execute the tests.