In this article, I will give a short (and very uncomplete) overview of the problems researchers try to deal with by utilising methods from the area of AI. Among the diverse methods used in the field of artificial intelligence, there are three core disciplines that might help in engineering better software:
Finding patterns in large amounts of data
A software project does not consist of source code artifacts only but also of huge requirement documents, architectural diagrams, tons of issues filed in some bug-tracking system, test-case specifications and corresponding test data, documentation and so forth. Hence, some software projects can be regarded as a big collection of data; in any case a bunch of projects, e.g. all accessible open source projects, can be definitely seen as big data in which one can search for interesing patterns. Machine learning and data mining are two subfields of AI that might help the software engineer by elevating intelligence already contained in existing artifacts. Predicting occurences of bugs based on bug-tracking data and software metrics is one example. Another one is intelligent code recommendations based on the large amount of existing code in open source repositories.Understanding natural language
One subfield of AI is natural language processing with its goal to make the machine understand the meaning of natural language. Especially the understanding of text-based information like requirement specifications or bug descriptions holds the potential of assisting the software engineer in certain applications like linking requirements to source code or finding duplicated bug reports. In this area, methods have evolved in the last decades from just using term frequencies for document comparisons to understanding which topic a text is about by making use of concepts from linear algebra and probability theory.Biology inspired search algorithms
Several problems in computer science are hard to solve, i.e. there is no exact solution that scales well when the input size increases. But often an approximate solution is good enough to work with and much more efficient to compute. In the area of evolutionary computing principles from biological evolution, like gene inheritance and mutation, are used to design algorithms that find good solutions by invoking a large number of computationally simple steps which is in the end faster than finding an exact solution, especially when the problem size increases. Evolutionary computing can be devided into two sub-areas, genetic algorithms and genetic programming. The goal of the former approach is to find a concrete solution for a problem (e.g. TSP), whereas the goal of the latter is to find a program, described by its syntax tree, that in turn solves a problem. Release planning and automated bug-fixing are only two areas of research where these kinds of algorithms are frequently used.In the following I will present some active research topics which are quite interesting from my personal point of view. The used references can be seen as starting points for getting more details. I sorted the topics by the typical software development stages:
Requirements / Planning
Release Planning
In release planning the goal is to select a number of requirements to be implemented for the next release of the software in a way that the customers’ satisfaction is maximized while staying within given bugdet/time boundaries. Furthermore, each customer has a different importance for the company and requirements are usually not independent from each other. In large-scale requirement scenarios this problem is hard to solve, hence intelligent search methods are required to find good (approximate) solutions. Often, genetic algorithms are used for this purpose, as in [1] and [2].Resource-constrained Project Scheduling
The goal of project scheduling is to assign tasks to available resources while minimizing costs. In software engineering this can be translated into assigning implementation tasks to developers with certain skillsets. This is a classic problem from operational research and is known to be NP-hard. Among the proposed approximation algorithms, here again genetic algorithms seem to be promising [3]. But also swarm intelligence methods like ant colony optimizations have been inspected in this area [4]. See also [5] for a detailed survey of proposed solutions.Implementation
Code Recommendations
Code completion is a frequently used tool not only for writing code faster, but also for exploring the functions an API provides. However, it is usually statically based on the used libraries which has some drawbacks. First, when the API is huge, the developer gets overwhelmed by the number of possible functions in a certain context, hence time gets wasted for searching the desired call. Second, the proper use of a function in a certain context is still not clear, so developers end up in trial and error workflows when working with new APIs. To make the system more intelligent, one can compute recommendations based on what other developers already coded in similar situations. The data basis for this knowledge can be gathered from open source repositories. In [6] a system is proposed which encodes the context of a variable by the methods in which it is used and by the methods previously called on that variable. The idea is then to find a number of similar code snippets in the code base by means of a modified k-Nearest-Neighbors approach and provide corresponding recommendations. The conducted research in [6] is also the basis for the popular Code Recommenders plugin in the Eclipse IDE.Testing / Bug-Fixing
Automated Bug-fixing
Once a bug is spotted by means of a failing test case, the idea of automated bug-fixing is to let the machine provide a suitable patch such that all test cases are green again. One way to do this is to use a genetic programming approach in which a lot of (initially nearly random) patches are tried and evaluated by running all test cases (see [7]). The best (but still not perfect) of these patches are then combined together and evaluated again. This process is repeated several times. Together with some random mutations, this strategy eventually finds a suitable patch for the bug under consideration. Additionally, the patch size is included in the evaluation process to drive the search towards smaller solutions. In [8] an algorithm is proposed which does not only mutate the code until a bug is fixed, but simultaneously evolves the unit tests based on how many bugs they find. This results in a competitive co-evolution, where the mutated programs try to catch up with the mutated unit tests.Bug Prediction
Classification is one of the basic tasks in machine learning: Given some input data, compute to which class this data belongs to by making use of learned relations from some training examples. Predicting bugs can be seen as a classification problem. Trained on previous occurences of bugs and some software metrics describing the quality of the buggy piece of code, a model can be constructed that predicts bugs or at least points to code snippets that have a higher chance of being buggy. Many of the typical machine learning approaches, like Naïve Bayes, Support Vector Machines or Logistic Regression are suitable for this problem. [9] gives an overview of the research conducted in this area and compares the proposed methods.Maintainance
Bug Management
In bug management, or bug triage, the existing bugs or issues are edited by assigning a suitable severity class, mapping issues to corresponding developers or detecting and marking duplicate entries. When many users are contributing to bug reports, their maintainance becomes a time consuming job. Intelligent tools can assist in categorizing new bug reports by learning from the existing ones. One can think of recommendations for severity classes based on the terms used in the bug description [10, 11]. Typical classification algorithms like Support Vector Machines can learn that terms like “crash” or “NPE” usually describe severe bugs. Since the data in these scenarios is unstructured text, the usual steps from information retrieval methods, like tokenization, stop-word removal and stemming need to be performed beforehand to yield good classification results.When the goal is to find duplicated bug reports, taking only the used terms and their frequencies might not be enough, as two reports may describe the same bug with completely different terms. Hence, the hidden semantic structure of a bug description (comparable to the topic of a text) needs to be revealed and used for comparison. This is investigated in [12] by using Latent Dirichlet Allocation to model the mapping between the terms of a bug report and the topic they belong to in a probablistic manner.
Traceability
In software engineering, traceability information describes how different artifacts are related to each other. For example, a requirement specification can be linked to the implementing source code, which in turn can be linked to a corresponding test case. One major advantage of maintaining this information is the possibility to perform impact analyses and thereby calculating the cost of a change in question. However, the maintaining overload can be a time consuming part in large software projects. There are several research proposals on how to alleviate this burden by automatically discovering relations between software artifacts [13, 14]. The current trend is to use advanced methods from information retrieval, like Latent Dirichlet Allocation, to represent an artifact in terms of the topics it is about [15]. Traceability links are then proposed based on the similarity of artifacts in their topic representation.This was only a very incomplete listing of research topics where methods of artificial intelligence (and especially its sub-fields machine learning, evolutionary computing and information retrieval) are used to help creating better software. But the goal here is just to give a broad overview and some starting reading material for the more intereseted readers who might also want to take a look at the RAISE workshop.
References
[1] Greer, D., & Ruhe, G. (2004). Software release planning: An evolutionary and iterative approach. Information and Software Technology, 46, 243–253.
[2] Zhang, Y., Harman, M., & Mansouri, S. (2007). The Multi-Objective Next Release Problem, 1129–1136.
[3] Hartmann, S. (2002). A self-adapting genetic algorithm for project scheduling under resource constraints. Naval Research Logistics, 49(5), 433–448.
[4] Merkle, D., Middendorf, M., & Schmeck, H. (2002). Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 6(4), 333–346.
[5] Kolisch, R., & Hartmann, S. (2006). Experimental investigation of heuristics for resource-constrained project scheduling: An update. European Journal of Operational Research, 174, 23–37.
[6] Bruch, M., Monperrus, M., Mezini, M., & Briand, L. (2009). Learning from examples to improve code completion systems. Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering on European Software Engineering Conference and Foundations of Software Engineering Symposium - E, 213.
[7] Weimer, W., Forrest, S., Le Goues, C., & Nguyen, T. (2010). Automatic program repair with evolutionary computation. Communications of the ACM, 53, 109.
[8] Arcuri, A., & Yao, X. (2008). A novel co-evolutionary approach to automatic software bug fixing. 2008 IEEE Congress on Evolutionary Computation, CEC 2008, 162–168.
[9] Hall, T., Beecham, S., Bowes, D., Gray, D., & Counsell, S. (2011). A Systematic Review of Fault Prediction Performance in Software Engineering. IEEE Transactions on Software Engineering, 38(6), 1276–1304.
[10] Lamkanfi, A., Demeyer, S., Soetens, Q. D., & Verdonckz, T. (2011). Comparing mining algorithms for predicting the severity of a reported bug. Proceedings of the European Conference on Software Maintenance and Reengineering, CSMR, 249–258.
[11] Tian, Y., Lo, D., & Sun, C. (2012). Information retrieval based nearest neighbor classification for fine-grained bug severity prediction. Proceedings - Working Conference on Reverse Engineering, WCRE, 215–224.
[12] Nguyen, A. T., Nguyen, T. T. T. N., Lo, D., & Sun, C. (2012). Duplicate bug report detection with a combination of information retrieval and topic modeling. Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering - ASE 2012, 70.
[13] Spanoudakis, G., & Zisman, A. (2005). Software traceability: a roadmap. Handbook of Software Engineering and Knowledge Engineering (Vol. III, pp. 1–35). Retrieved from http://soi.city.ac.uk/~gespan/hseke05.pdf
[14] Oliveto, R., Gethers, M., Poshyvanyk, D., & Lucia, A. De. (n.d.). ICPC10：On the equivalence of information retrieval methods for Automated Traceability Link Recovery.
[15] Asuncion, H. U., Asuncion, A. U., & Taylor, R. N. (2010). Software traceability with topic modeling. 2010 ACM/IEEE 32nd International Conference on Software Engineering, 1(May), 95–104.
Keine Kommentare:
Kommentar veröffentlichen