Generating Configuration Models from Requirements to Assist in Product Management – Dependency Engine and its Performance Assessment Juha Tiihonen1 and Iivo Raitahila1 and Mikko Raatikainen1 and Alexander Felfernig2 and Tomi Männistö1 Abstract. Requirements engineering is often, especially in the con- ments to be implemented simultaneously might need to follow all text of major open source software projects, performed with issue dependencies transitively, which is not readily supported by the is- tracking systems such as Jira or Bugzilla. Issues include require- sue trackers. The issue trackers are not either necessarily optimal for ments expressed as bug reports, feature requests, etc. Such systems the concerns of product or release management that need to deal with are at their best at managing individual requirements life-cycle. The different requirement options, alternatives and constraints, as well as management of dependencies between issues and holistic analysis their dependency consequences when deciding what to do or not to of the whole product or a release plan is usually scantly supported. do. However, dependencies in general are found to be one of the key Feature modeling is an established way to represent dependencies concerns that need to be taken into account, e.g., in requirements pri- between individual features, especially in the context of Software oritization [1, 9, 18] and release planning [2, 17]. In fact, the above Product Lines — well-researched feature model analysis and con- concerns are not at the core of issue trackers’ support for the require- figuration techniques exist. We developed a proof-of-concept depen- ments engineering activity. Rather, issue trackers focus more on a dency engine for holistically managing requirements. It is based on single issue, its properties, and its life cycle. The situation is not nec- automatically mapping requirements and their dependencies into a essarily specific only for issue trackers, but it exists also in other variant of feature models, enabling utilization of existing research. kinds of RMS. The feature models are further mapped into a constraint satisfaction In the context of a Horizon 2020 project called OpenReq, we de- problem. The user can experiment with different configurations of veloped a proof-of-concept Dependency Engine for holistically man- requirements. The system maintains the consistency of dependencies aging requirements as a single model. It is based on automatically and resource constraints. To evaluate the feasibility of the system, we mapping requirements and their existing isolated dependencies into measure the performance of the system both with some real and gen- the Kumbang [3] variant of feature models, enabling utilization ex- erated requirements. Despite some remaining performance issues, it isting research. A feature model is further mapped into a constraint seems that the approach can scale into managing the requirements of satisfaction problem. The user can experiment with different config- large software projects. urations of requirements. The system maintains the consistency of dependencies and resource constraints. This paper outlines the principle of the Dependency Engine and 1 INTRODUCTION addresses its feasibility in terms of performance. We measure the There are various kinds of requirement management systems (RMS) performance of the system both with some real and generated re- applied in requirements engineering [10]. In particular, different is- quirements. Responsive performance is important for interactive us- sue tracker systems, in which requirements are captured as issues, age, e.g., what-if analysis of requirements to include in a release. are becoming increasingly popular, especially in large-scale, glob- Furthermore, it is important that decisions are based on current in- ally distributed open source projects, such as in the cases of Bugzilla formation; either relatively fast model generation or a way to update for Linux Kernel, Github tracker for Homebrew, and Jira for Qt. An models ’on-the-fly’ are required. issue tracker can contain tens of thousands requirements, bugs and The rest of the paper is organized as follows. Section 2 outlines other items that are different ways interdependent from each other. the concept of a feature model. Section 3 presents the research ques- Issue tracker systems as RMSs provide primarily with support tions, general idea of the Dependency Engine, applied data and tests. for individual requirements throughout various requirements engi- Section 4 presents the results, Section 5 provides analysis and dis- neering activities, such as requirements documentation, analysis, and cussion. Finally, Section 6 concludes. management as well as tracking the status of a requirement over its life cycle. Even though individual dependencies, including more ad- vanced constraints, can be expressed in the case of an individual re- 2 BACKGROUND: FEATURE MODELING quirement, more advanced analysis over all requirements of a system The notion of a feature model, similarly as a requirement, is not un- taking into account the dependencies and properties of the require- ambiguous. A feature of a feature model is defined, e.g., as a char- ments is not well supported. For example, deciding a set of require- acteristic of a system that is visible to the end user [12], or a system 1 University of Helsinki, Finland, first.last@helsinki.fi property that is relevant to some stakeholder and is used to capture 2 Graz University of Technology, Austria, alexander.felfernig@ist.tugraz.at commonalities or discriminate among product variants [8]. A feature model is a model of features typically organized in a tree-structure. One feature is the root feature and all other features are then the subfeatures of the root or another feature. Additional relationships are expressed by cross-branch constraints of different types, such as requires or excludes. Feature model dialects are not always precise about their semantics, such as whether the tree constitutes a part-of or an is-a structure [19]. Despite this, feature models have also been provided with various formalizations [8, 16] including a mapping to constraint programming [5, 6]. Specifically, we apply the Kumbang feature model conceptualiza- tion [3] as the basis. It has a textual feature modeling language and it has been provided with formal semantics. Kumbang specifies sub- features as part-of relations and allows defining separate is-a hier- archies. Kumbang supports feature attributes and its constraint lan- guage can be used to express cross-branch relationships. A feature model is a variability model roughly meaning that there are optional and alternative features to be selected, and attribute val- ues to be set that are limited by predefined rules or constraints. When variability is resolved, i.e., a product is derived or configured, the result is a configuration. Variability is resolved by making configura- tion selections such as an optional feature is selected to be included, or one of alternatives is selected. A consistent configuration is a con- figuration in which a set of selections have been made, and none of the rules have been violated. A complete configuration is a consistent configuration in which all necessary selections are made. Feature modeling has become a well-researched method to man- age variability and has been provided with several different analyses to assist in system management [4]. Figure 1. Workflows of the Dependency Engine 3 METHODS AND DATA Milla is a front-end that is used to access requirement data via We follow Design Science in the sense that the aim is to innovate volatile or case-dependent interfaces. For example, it extracts re- a novel intervention and bring it into a new environment so that the quirements via the API of Jira. It outputs MulSON, a JSON based results have value in the environment in practice [11]. Dependency intermediate transfer format understood by Mulperi. engine is the artifact of the intervention and this paper focuses on its Mulperi converts from a small number of stable requirement in- quality attributes. The specific research questions are: put formats such as MulSON into the Kumbang feature modeling language. It can generate a number of queries to SpringCaaS. • RQ1: Can the OpenReq Dependency Engine scale to real-world SpringCaaS takes as input Kumbang feature models and converts projects? them into a corresponding Constraint Satisfaction Problem (CSP). • RQ2: How can the performance of the Dependency Engine be Choco Open-Source Java library for Constraint Programming [15] improved? was selected because it is Java-based, popular, and has good per- formance and a permissive license. The Kumbang model and corre- 3.1 Approach and architecture sponding the data structures are saved for subsequent use. To facilitate requirement management via a feature-based approach, we make each requirement correspond to exactly one feature. The 3.2 Potential bottlenecks and related tests properties of a requirement correspond to the attributes of a feature. Network and external system bottlenecks Jira integration The dependencies of individual requirements are mapped to hierar- fetches requirements from the RMS one requirement at a time chies and constraints of a feature model. We currently rely only on over network, which can potentially create performance bottlenecks. the dependencies explicitly expressed in requirements although we These bottlenecks are outside the scope of this paper4 . will aim to extract missing dependencies with NLP technologies. In order to make such a mapping, we need a feature model dialect that is conceptually relatively expressive supporting feature typing and Requirement model generation Milla generates feature models attributes. Kumbang was selected for this purpose. from requirements data fetched from Jira. Effectively, relevant data, The Dependency Engine currently consists of three stand-alone such as IDs, dependencies and the attributes that are needed in infer- software components with specific responsibilities: Milla, Mulperi ence, are extracted and a MulSON presentation is generated. and SpringCaaS, see Figure 1. There are two different workflows: creating a model from requirements data and making subsequently Feature model generation A requirement model expressed in queries against the model. These three components operate as REST- MulSON is sent to Mulperi. Mulperi generates a feature model ex- type services and are implemented using the Java Spring framework3 . pressed in the Kumbang feature modeling language. Mulperi’s func- 3 https://spring.io/ 4 Bottlenecks were identified and solved by adding parallel connections. tionality is largely based on data structure manipulation - JSON input 3.3.2 Synthetic data and Kumbang output. The transformation is straightforward. Mulperi also saves the results into an in-memory database. This model is then The synthetic datasets were created and run using automated scripts. sent to SpringCaaS in a single message. SynData1 dataset contains a total of 450 models with permutations of the amounts of requirements (from 100 to 2000), a ’requires’ de- pendency (from 0 to 75% of the requirements), an optional subfea- Feature model to CSP A feature model expressed in Kumbang is ture with one allowed feature (from 0 to 75% of the requirements) parsed. Kumbang syntax resembles many programming languages. and a number of attributes (from 0 to 5 per requirement); each at- Therefore parsing is potentially heavy. tribute has two possible values, e.g., 10 and 20. Based on the data structures representing the feature model, a cor- A smaller dataset (60 test cases), SynData2, was used for opti- responding Constraint Satisfaction Problem (CSP) is generated. Ba- mization tests with sum constraints, see Section 3.4.5. SynData2 sically, a set of Boolean CSP variables represents instances of indi- contains models with permutations of the amounts of require- vidual feature types. Each of these is related to corresponding integer ments (from 100 to 2000), a ’requires’ dependency (from 0 to CSP variables that represent attribute values of these individual fea- 75% of the requirements), no further subfeatures and 1 or 2 at- tures. Enumerated strings are mapped to integers. Choco constraints tributes with a fixed random value from 1 to 100. An example of are created based on the dependencies; the constraints can access the a SynData2requirement in MULSON format: presence of a feature, and relationships between attribute values of features. The current implementation supports only binary relation- { "requirementId": "R4", ships (requires, excludes). "relationships": [ { In addition, it is possible to specify global resource (sum) con- "targetId": "R25", "type": "requires" straints over specific attributes. For example, the sum of efforts of } included features can be constrained. To facilitate this, the imple- ], "attributes": [ mentation reserves attribute value 0 to attribute values of features { "name": "attribute1", that are NOT in configuration. "values": ["9"], "defaultValue": "9" },{ "name": "attribute2", CSP solving The prime suspect for performance bottlenecks is "values": ["22"], "defaultValue": "22" solving the CSP representing a model of requirements. There are a } ], number of tasks to accomplish based on a constructed model. "name": "Synthetic requirement nro 4" } • check a configuration of features for consistency • complete a configuration of features 3.4 Empirical tests • determine the consequences of feature selections 3.4.1 Test setup The selection of search strategy often has significant effect on solvability and quality of solutions [15]. Measurements should be conducted when the software’s behaviour is typical[13]. Since there is currently no production environment, the tests are conducted on a development environment that closely re- 3.3 Data sembles the possible production environment. Furthermore, we aim The performance evaluations are based both on real data from the Qt to perform tests that could correspond to real usage scenarios. company and synthetic data. The test machine is an Intel Core i5-4300U 1.9GHz dual core lap- top with 16GB of RAM and an SSD disk, running Ubuntu Linux 16.04 and a 64-bit version of Oracle Java 1.8.0. All software compo- 3.3.1 Real requirements nents except for Jira are run on the same machine. Qt is a software development kit that consists of a software frame- The examined software components log execution times to files work and its supporting tools that are targeted especially for cross- that are collected after each automated test run. A timeout was set to platform mobile application, graphical user interface, and embedded limit the solving of Choco in SpringCaaS. application development. All requirements and bugs of Qt are man- Although SpringCaaS is a single component, we often report the aged in the Qt’s Jira5 that is publicly accessible. Jira6 is a widely used execution time in two parts: Choco Solver and the rest of Spring- issue tracker that can contain many issue types and has a lot of func- CaaS. This is because often Choco’s solve operation takes the most tionality for the management of issues. Issues and bugs can be con- time, but the initial tests showed that the Kumbang parser becomes a sidered as requirements and they have dependencies and attributes bottleneck in specific situations. with constant values, such as priority and status. Thus, known re- quirements and their dependencies have already been identified and 3.4.2 Initial trials and initial search strategy entered into Jira. Qt’s Jira contains 18 different projects and although some of the projects are quite small and discontinued, QT-BUG as Initial testing was performed with the goal to complete a configura- the largest project contains currently (April 2018) 66,709 issues. tion of requirements with a minimal number of additional require- For empirical evaluation with real data, a set of issues was gath- ments. The pareto optimizer of Choco was applied to provide alter- ered from Qt’s Jira and processed through the whole pipeline. Only native solutions7 . All features were included in the pareto front. By well-documented requirements having dependencies were selected default, Choco uses the domOverW Deg search strategy for interger to the dataset JiraData that contains 282 requirements. and Boolean variables [15]. Table 3 describes the search strategies 5 https://bugreports.qt.io 7 Pareto optimizer dynamically adds constraints: a solution must be strictly 6 https://www.atlassian.com/software/jira better than all previous solutions w.r.t. at least one objective variable [15]. applied. In our domain and way of modeling, the strategy effectively minDomLBSearch, see Table 3. These were augmented with leads to selection of excessive number of features. This is contrary to bestBound, lastConf lict or both; e.g., bestBound adds directs the initial goal. As results in the beginning of Section 4 will show, an search based on the objective function and a strict consistency check. alternative search strategy was required to achieve satisfactory per- formance. The Search Strategy was changed to minDomLBSearch; it Table 1. Resource constraints for optimization tests is used in the rest of the tests unless otherwise mentioned. Constraint# P Constraint 0 P attribute1 > 1000 3.4.3 Requirement model generation 1 P attribute1 = 1000 2 attribute1 P< 1000 JiraData and SynData1 Datasets were applied to run the whole P pipeline from gathered requirements to a Kumbang textual model 3 P attribute1 > 1000 ∧ P attribute1 < 2000 4 attribute1 > 1000 ∧ attribute2 < 2000 and a serialized feature model. The process is illustrated at the left hand side of Figure 1. The different steps were timed. In the case of SynData1 dataset, Milla was bypassed because the test cases were expressed directly in MULSON. Note that model gen- Table 2. Constraints, number of attributes and usage scenarios eration includes finding a consistent configuration of features; this search is performed as a form of a model sanity check. Constraint# #attributes Optimization goal 0, 1, 3 1 Simulate achieving desired utility with a minimal number of requirements to imple- 3.4.4 Requirement configuration ment. Minimizes the number of require- ments. Autocompletion of configurations was performed with the 2 1 Check the consistency of a given partial JiraData dataset. A run was performed with a sum calcula- configuration with respect to maximum ef- tion constraint. Here, each requirement has a numerical priority fort and complete the configuration with as few requirements as possible. Minimizes attribute. The query instructed SpringCaaS to give a configuration the number of requirements. In the case of where the sum of these priority attributes was greater than 100. SynData2, the test is redundant, only the More substantially, requirement configuration was also performed root feature will be included. with the SynData1 dataset to analyse the performance under vary- 4 1 (Not relevant, 2 attributes in constraint, 1 in model) ing number of requirements and their properties (attributes, depen- 0, 1, 2, 3 2 Simulate maximisation of utility under dencies), and user-specified requirements. This test applies optimiza- resource constraint: Maximize sum of tion to find a (close to) minimum configuration that includes pre- attribute2 selected features, if any. Effectively, the configuration of require- 4 2 Minimize the number of requirements to im- ments is completed. This is presumably one of the computationally plement under constraints of minimum util- ity and maximum effort. most intensive operations. The configuration phase is tested in ten it- erations: first selecting only one requirement and then increasing the number of selected requirements by 10% so that the tenth iteration has 1 + 90% requirements selected. 4 RESULTS 3.4.5 Optimised release configuration under resource The results of the initial trials are in the two first rows of Table 4. The constraint timeout and solution limits were disabled. The processing time was unacceptable, as reflected in the results. We performed a number of resource-constrained optimization tests. Here, we applied global sum (resource) constraints specified in Ta- ble 1 to constrain the allowed solutions. SynData2 Dataset contains 4.1 Requirement model generation test cases with 1 or 2 attributes per requirement (see Section 3.3.2). The first two rows of Table 6 present the results of processing the Effectively, the combination of number of attributes and the applied JiraData dataset through the whole pipeline. Table 5 shows the re- constraint correspond to usage scenarios presented in Table 2. Fi- sults of processing the SynData1 dataset. A save operation includes nally, we applied the bestBound(minDomLBSearch()) search finding a consistent non-optimized configuration of requirements. strategy, after we had experimented with different alternatives, see Figure 2 presents cases with 1000 requirements. Each bar color Section 3.4.6 and corresponding results. corresponds to a test case with a specific number of dependencies We run the tests with 60s, 10s and 3s timeout values to see the (from 0 to 200) and subfeatures (from 200 to 1000). The elapsed effect of allowed time on the solvability and to get an impression on time in Mulperi, SpringCaaS and Choco are shown for 0, 2000 and the quality of solutions. In addition, we developed and experimented 5000 attributes, that is, 0, 2 or 5 attributes per feature, each with two with a custom algorithm that (roughly) first ’filled’ effort bounds with possible values per requirement. ’big’ features and used ’small’ ones to meet the bound. Figure 3 depicts a case with 1000 requirements and different num- ber of subfeatures (a requirement can be a subfeature of many re- quirements). Please note the logarithmic scale. With 5000 subfea- 3.4.6 Determining search strategy tures it took over five hours to parse the model. We tested a set of different search strategies for performance, Starting from (some) models with 1000 requirements, the serial- utilizing the 2000 requirement test cases of the SynData2 ization of the parsed Kumbang model failed due to a stack overflow dataset. The experimented basic search strategies included error. It was necessary to increase the Java Virtual Machines stack activityBasedSearch, Choco default domOverW Deg, and size to one gigabyte to prevent out-of-memory errors. Table 4. Effect of search strategy with Pareto optimizer, JiraData dataset Strategy Optional features Mandatory features Attributes Solutions Time default 14 0 0 60 130 to 300 ms default 20 0 0 1046 11600 to 11900 ms (unacceptable) minDomLBSearch 14 0 0 1 120 to 170 ms minDomLBSearch 20 0 0 1 150 to 190 ms minDomLBSearch 235 0 2 per feature 1 160 to 200 ms minDomLBSearch 118 117 2 per feature 1 400 to 650 ms Table 5. Minimum, maximum and median test cases of the save phase, SynData1 dataset Requirements Dependencies Subfeatures Attributes Mulperi time (ms) SpringCaaS time (ms) Choco time (ms) Total time (ms) 500 375 200 0 85 158 98 341 500 50 500 1000 504 247 493 1244 500 250 500 2500 1971 439 2133 4543 750 563 150 0 159 220 401 780 750 375 0 1500 1040 371 2239 3650 750 563 1125 3750 4988 684 6359 12031 1000 750 400 0 309 347 670 1326 1000 750 0 2000 1895 584 4144 6623 1000 750 1500 5000 8859 1029 12772 22660 1500 1125 600 0 584 509 2009 3102 1500 0 1500 3000 4942 733 8756 14431 1500 750 2250 7500 21747 1738 30270 53755 2000 1000 800 0 661 566 4781 6008 2000 1500 0 4000 6958 1079 15816 23853 2000 1500 2000 10000 37692 2018 46433 86143 Table 3. Choco Search strategies Search strategy Description activityBasedSearch Search strategy for ”black-box” constraint solving. ” ... the idea of using the activity of variables during propagation to guide the search. A variable activ- ity is incremented every time the propagation step filters its domain and is aged.”[14]. Used parame- ters (GAMMA=0.999d, DELTA=0.2d, ALPHA=8, RESTART=1.1d, FORCE SAMPLING=1) [15] Figure 2. Performance effect of attributes domOverWDeg Choco default. ”Intuitively, it avoids some trashing by first instantiating variables involved in the con- straints that have frequently participated in dead- end situations” [7]. Slightly oversimplifying, the strategy attempts to solve hard parts of a CSP first, weighting constraints by their participation in dead-ends. minDomLBSearch ”Assigns the non-instantiated variable of smallest domain size to its lower bound” [15] bestBound Search heuristic combined with a constraint per- forming strong consistency on the next decision variable and branching on the value with the best objective bound (for optimization) and branches on the lower bound for SAT problems.[15] lastConflict ”Use the last conflict heuristic as a plugin to im- prove a former search heuristic Should be set after specifying a search strategy.”[15] Figure 3. Kumbang parser’s fatigue Table 6. Measurements from the whole pipeline, JiraData dataset Function Requirements Request Milla time Mulperi time SpringCaaS time Save model 1 - 0,182 s 0,010 s 0,050 s Save model 282 - 1,252 s 0,311 s 0,315 s Configure 1 empty - 0,050 s 0,005 s Configure 282 empty - 0,050 s 0,143 s Configure 282 10 features - 0,040 s 0,172 s Configure 282 25 features - 0,077 s 0,127 s Configure 282 50 features - 0,116 s 0,099 s Configure 282 10 features with dependencies - 0,040 s 0,093 s Configure 282 sum calculation constraint - - 5,098 s (timeout) Table 7. Minimum, maximum and median test cases of the configuration phase, SynData1 dataset Requirements Dependencies Subfeatures Attributes Requirements in request Mulperi (ms) SpringCaaS (ms) Choco (ms) Total (ms) 100 10 0 0 1 9 10 4 23 100 10 20 200 91 10 21 8 39 100 0 0 500 1 27 54 14 95 500 0 100 0 451 34 79 19 132 500 100 200 0 101 33 61 71 165 500 0 0 2500 201 34 266 549 849 750 0 150 0 601 60 122 55 237 750 0 150 1500 376 63 156 344 563 750 375 0 3750 601 70 273 1614 1957 1000 750 1000 0 1 129 133 126 388 1000 500 0 2000 401 90 252 777 1119 1000 0 0 0 1 1344 414 1788 3546 1500 0 0 0 1351 186 363 179 728 1500 0 0 3000 751 185 364 2159 2708 1500 300 0 7500 1351 263 715 9087 10065 2000 0 0 0 1801 237 619 334 1190 2000 200 0 4000 801 297 515 4445 5257 2000 1000 0 10000 1801 573 1056 16464 18093 Figure 4. Performance effect of dependencies, 1500 requirements Figure 5. Performance effect of selected requirements and unselected attributes 4.2 Requirement configuration 4.3 Optimized configuration under resource The results of the configuration task with the JiraData dataset are constraint from row 3 onwards in Table 6. In case of the sum constraint (the last row), SpringCaaS was able to find 107 to 120 solutions before the Table 8 presents a summary of the results of test that minimize the timeout at 5s was reached. number of features. Note that constraint #4 is from test cases with 2 Table 7 contains the minimum, maximum and median measure- attributes, the others apply to test cases that have one attribute that ments of total execution times for varying numbers of requirements, is constrained. Because all features are optional, tests with constraint dependencies, subfeatures, attributes and number of pre-selected re- #1 trivially contain only the root feature of the model. quirements in the request. Table 9 represents the results of optimizing via Maximization of Figure 4 shows the effect of the number of dependencies in case the sum of attribute 2 (e.g. utility) under constraints on attribute1. of 1500 requirements per test case, but with a varying number of Test cases with 100, 500, 750, 1000, 1500 and 2000 requirements requires-dependencies. and varying numbers of requirements are solvable with 60s timeout. Figure 5 shows the effect of the number of requirements and at- 10s handles all cases except 2000 requirements. 3s timeout is only tributes in case of 1500 and 2000 requirements per test case. applicable to cases with 100, 500 and 750 requirements. Table 8. Minimization of the number of features. Results of 60 second timeout compared with 10 and 3 second timeouts and the custom algorithm. Lower number of features in a solution is better. T est: the type of the testcases, #a: the number of attributes in the test cases. N : the average number of features in the minimal solution found with the 60s timeout. N=10 : the number of test cases where 10s timeout search finds the same number of features than the 60s version. N>10 : the number of test cases where 10s timeout search includes a larger number of features than the 60s version. ∆N10 : the average number of additional features included in a solution found with 10s timeout when compared to the 60s search. ∆N10 (%): the average percentage of additional included features found by the 10s version. N=3 , N>3 , ∆N3 , ∆N3 (%): 3 second timeout versions analogously as 10s. The corresponding figures of the custom algorithm are presented similarly: N=c , Nc , ∆Nc (%). Note that N10 ∆N10 ∆N10 (%) N=3 N>3 ∆ N3 ∆N3 (%) N=c Nc ∆Nc (%) 0 1 14.3 14 11 0.48 3.38% 7 8 0.60 4.92% 4 7 19 2573.33% 1 1 14.3 14 11 0.52 3.63% 7 8 0.67 4.92% 6 4 20 106.67% 2 1 1.0 25 0 0.00 0.00% 15 0 0.00 0.00% 30 0 0 0.00% 3 1 14.3 13 12 0.52 3.65% 7 8 0.73 4.92% 4 7 19 620.00% 4 2 14.4 17 8 0.32 2.26% 6 9 0.67 4.40% 0 0 30 1456.67% A memory of 3 GB was required to complete the tests. The Requirement model generation The number of dependencies be- bestBound search strategy became feasible by applying the opti- tween the requirements seem to have no impact during the save mization to one variable or to the sums of attributes. A pareto front phase. To avoid out-of memory errors, Kumbang model read and with all feature variables caused excessive memory consumption. write methods could be overridden with an implementation that suits better for the Kumbang data structure, or the serialization phase 4.4 Determining search strategy could be omitted altogether. On the other hand, optimized solving needs even more memory. Table 10 compares search strategies with 2000 require- Increasing the number of attributes increases the processing time ment test cases and minimization tasks. def aultSearch and of each component steadily, see Figure 2. Increasing the amount activityBasedSearch fail in a number of cases with 60s timeout.8 of subfeatures increases the processing time of Mulperi and Choco minDomLBSearch can solve all these cases. Negative ∆N steadily as well, but when the amount of subfeatures is very large, indicates that the compared search strategy found better solutions the Kumbang parser slows down drastically, see Figure 3. (e.g. Total number of features was 18 less in the 30 tests) . Constraint #2 with 2 attributes is essentially uncon- Requirement configuration The results in Section 3.4.4 suggest strained for big problems. Here, the optimal solution in- that a five second timeout would be sufficient for models with about cludes all features. Plain minDomLBSearch fails to 500 requirements or less. The configuration of all 1000 requirement ’notice’ that. Both bestBound(minDomLBSearch()) models and most of the 1500 requirement models can be performed and lastConf lict(bestBound(minDomLBSearch())) in less than five seconds. help the solver to find the maximal solution. Of The timeout value of the save phase could be set to be longer. Both these, in terms of maximized result on attribute2, timeout values could be controlled with parameters, for example if bestBound(minDomLBSearch()) is slightly better in 3 the user thinks that he/she can wait for a full minute for the process- cases and lastConf lict(bestBound(minDomLBSearch())) in ing to complete. During the configuration phase, the dependencies one. Due to limitations of space, further details are omitted. actually ease Choco’s inference burden. Figure 4 with 1500 require- Earlier tests with all features in the pareto front prevented the us- ments shows that when there are no dependencies, the preselected age of bestBound strategy due to increased memory consumption. requirements in the configuration request speed up Choco linearly. The increase in configuration request size adds processing over- Table 10. Comparison of search strategies with 2000 requirement cases head to SpringCaaS. Secondly, when the dependency rate gets and Minimization tasks with 60s timeout Search Strategy # no so- ∆N higher, more requirements are included in the configuration early on, lution again helping Choco perform faster. The same is true for subfeatures: minDomLBSearch() 0 0 lastConf lict(minDomLBSearch()) 0 -12 selecting requirements with subfeatures decreases processing time. bestBound(minDomLBSearch()) 0 -18 With attributes, the situation is the opposite. The more there are lastConf lict(bestBound(minDomLBSearch())) 0 -18 def aultSearch() 20 attributes and the more configuration request contains selected re- bestBound(def aultSearch()) 45 quirements, the more time it takes to select attributes, see Figure 5. activityBasedSearch() 50 bestBound(activityBasedSearch()) 49 The optimization task is computationally intensive. It is difficult lastConf lict(bestBound(activityBasedSearch())) 49 for the solver to determine if an optimal solution has been found. Therefore solving practically always ends with a timeout. Optimised release configuration under resource constraint 5 ANALYSIS AND DISCUSSION When a solution is found, the versions with a lower timeout value Initial trials The results of Table 4 turned out to be too good: remain almost as good as solutions obtained with 60s timeout. The it happens that the minimal requirement configurations of models in custom algorithm was expected to perform well in test case types 1 JiraData are unique. That is, the solver can find a minimal solution and 2. However, this seems not be the case. Out of 150 test cases, the with MinDomLBSearch and even prove its optimality. algorithm finds better solutions than the the ’normal’ minimizer in 8 This test was performed with a different, weaker computer than the nor- 18 cases. In the clear majority of cases, it performs worse. mally used one. Table 9. Maximization of sum of attribute 2 (e.g. utility). Results of 60 second timeout compared with 10 and 3 second timeouts. The custom algorithm is excluded. Higher sum of attribute 2 (a2) is better. T est: the type of the testcases, #a: the number of attributes in the test cases. N60 : the average number of features in a solution found with the 60s timeout. a160 , a260 :average value of attribute 1 / attribute 2 in solutions identified with 60s timeout, respectively. N10,a2,< and N10,a2,= : the number of test cases where 10s timeout search finds a lower / same same sum of attribute 2 than the 60s version, respectively. ∆N10 (%) : the average difference (percentage) between number of included features between 60s and 10s timeout versions. ∆a210 (%): the average difference (percentage) between sum of attribute 2 of included features between 60s and 10s timeout versions. 3 second timeouts are analogous, SynData2. T est #a N60 a160 a260 N10,a2,< N10,a2,= ∆N10 (%) ∆a210 (%) N3,a2,< N3,a2,= ∆N3 (%) ∆a23 (%) 0 2 976 48979 49255 0 25 0.0% 0.0% 0 15 0.0% 0.0% 1 2 33.2 1000 1821 24 1 -2.1% -4.1% 15 0 -2.9% -5.9% 2 2 33.5 998 1831 21 4 -3.4% -4.6% 13 2 -5.7% -6.5% 3 2 53.6 1998 2860 23 2 -2.1% -3.2% 15 0 -3.6% -4.5% Determining search strategy The best search strategy for our [3] Timo Asikainen, Tomi Männistö, and Timo Soininen, ‘Kumbang: A do- purposes is bestBound(minDomLBSearch()) instead of plain main ontology for modelling variability in software product families’, Advanced Engineering Informatics Journal, 21(1), (2007). minDomLBSearch(), because it provides slighly better results in [4] D. Benavides, S. Segura, and A. Ruiz-Cortes, ‘Automated analysis of minimization tests and maximizes significantly better. feature models 20 years later: A literature review’, Information Systems, 35(6), 615–636, (2010). [5] David Benavides, Pablo Trinidad, and Antonio Ruiz-Cortes., ‘Auto- 6 CONCLUSIONS mated reasoning on feature models’, in 17th Conference on Advanced Information Systems Engineering (CAiSE), (2005). Solutions without optimization are easy to find; solvers such as [6] David Benavides, Pablo Trinidad, and Antonio Ruiz-Cortes, ‘Using Choco have an easy task with sparse dependencies. Still, at least for constraint programming to reason on feature models’, in International Conference on Software Engineering and Knowledge Engineering, optimization, the selection of a search strategy matching the prob- (2005). lem at hand remains crucial. It was surprising that the ”black-box” [7] Frédéric Boussemart, Fred Hemery, Christophe Lecoutre, and Lakhdar activityBasedSearch[14] and Choco default domOverWDeg[7] did Sais, ‘Boosting systematic search by weighting constraints’, in Pro- not perform in a satisfactory way. ceedings of the 16th European Conference on Artificial Intelligence, The prototype engine easily scales to around 2000 requirements, pp. 146–150. IOS Press, (2004). [8] K. Czarnecki, S. Helsen, and U. W. Eisenecker, ‘Formalizing even when optimization is desired. Despite some remaining perfor- cardinality-based feature models and their specialization’, Software mance issues, it seems that the approach can scale into managing the Process: Improvement and Practice, 10(1), 7–29, (2005). requirements of large software projects, even for interactive use. [9] Maya Daneva and Andrea Herrmann, ‘Requirements prioritization However, very large software projects, such as QT-BUG remain based on benefit and cost prediction: A method classification frame- work’, in 34th Euromicro Conference on Software Engineering and Ad- challenging. A more close examination of the Qt Jira is required, be- vanced Applications (SEAA), pp. 240–247, (2008). cause it seems that performance can be managed in various ways. [10] Juan M. Carrillo de Gea, Joaqun Nicols, Jos L. Fernndez Alemn, Am- First, there are different types of issues such as bugs and require- brosio Toval, Christof Ebert, and Aurora Vizcano, ‘Requirements en- ments that do not need to be considered at the same time. Second, Qt gineering tools: Capabilities, survey and assessment’, Information and has used Jira over a decade and there is a lot of historical data. The Software Technology, 54(10), 1142 – 1157, (2012). [11] S. Gregor, ‘The nature of theory in information systems’, MIS Quar- rate of new Jira issues seems to be up to 20 per a day. So, consider- terly, 30(3), 611–642, (2006). ing only issues created or modified within three years would signifi- [12] K.C. Kang, S.G. Cohen, J.A. Hess, W.E. Novak, and A.S. Peterson, cantly decrease the amount of data. Third, the exact nature of Qt data ‘Feature-oriented domain analysis (FODA) feasibility study’, Technical and practical applications need to be inspected in more detail; now Report CMU/SEI-90-TR-21, Software Engineering Institute, (1990). [13] D. Maplesden, E. Tempero, J. Hosking, and J. C. Grundy, ‘Performance it seems that only about 10% of issues have dependencies, and the analysis for object-oriented software: A systematic mapping’, IEEE compositional hierarchy such as epics decomposed to smaller items Transactions on Software Engineering, 41(7), 691–710, (July 2015). needs a few levels at most. [14] Laurent Michel and Pascal Van Hentenryck, ‘Activity-based search The concept of Dependency Engine is novel and it seems to be for black-box constraint programming solvers’, in International Con- feasible for its intended use for providing holistic support for the ference on Integration of Artificial Intelligence (AI) and Operations Research (OR) Techniques in Constraint Programming, pp. 228–243. management of dependencies, also in the context of large software Springer, (2012). projects. [15] Charles Prud’homme, Jean-Guillaume Fages, and Xavier Lorca, Choco Documentation, TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S. www.choco-solver.org, 2016. ACKNOWLEDGEMENTS [16] P-Y. Schobbens, P. Heymans, J-C. Trigaux, and Y. Bontemps, ‘Generic semantics of feature diagrams’, Compututer Networks, 51(2), (2007). This work has been funded by EU Horizon 2020 ICT-10-2016 grant [17] Mikael Svahnberg, Tony Gorschek, Robert Feldt, Richard Torkar, No 732463. We thank the Qt Company for sharing the data. Saad Bin Saleem, and Muhammad Usman Shafique, ‘A systematic re- view on strategic release planning models’, Information and Software Technology, 52(3), 237 – 248, (2010). [18] R. Thakurta, ‘Understanding requirement prioritization artifacts: a sys- REFERENCES tematic mapping study’, Requirements Engineering, 22(4), 491–526, (2017). [1] Philip Achimugu, Ali Selamat, Roliana Ibrahim, and Mohd Nazri [19] Juha Tiihonen, Mikko Raatikainen, Varvana Myllärniemi, and Tomi Mahrin, ‘A systematic literature review of software requirements prior- Männistö, ‘Carrying ideas from knowledge-based configuration to soft- itization research’, Information and Software Technology, 56(6), 568– ware product lines’, in International Conference on Software Reuse, pp. 585, (2014). 55–62, (2016). [2] David Ameller, Carles Farré, Xavier Franch, and Guillem Rufian, ‘A survey on software release planning models’, in Product-Focused Soft- ware Process Improvement, (2016).