Optimization Software Fault Injection by Using Two- Dimensional Bin Packing Algorithms

Abstract

Software fault injection has been used for decades to study different software representing a very wide spectrum ranging from simple algorithms that perform specific string operations to highly complex software such as operating systems especially Linux kernels. However, the current body of literature has revealed that software fault injection is less frequently used in the context of optimization algorithms with the aim of quantifying the worst-case scenarios and incorporating fault-tolerant mechanisms in such algorithms. Although defects in optimization algorithms have no life-critical consequences in most cases, they can lead to tremendous loss of resources (money, time, raw material, etc) since the primary objective of optimization algorithms is to utilize resources in the most efficient and effective way. In this study, a computationally complex optimization problem known as the two- dimensional bin packing problem is investigated. Three packing algorithms for the two-dimensional bin packing problem are studied from the perspective of software fault injection with the aim of understanding the potential risk associated with these algorithms which is represented by the worst-case scenario and to incorporate fault-tolerant mechanisms. Code mutation is used to perform the fault injection as it is the most accurate approach. The results show that common programming mistakes can lead to highly serious implications and result in significant resource loss. It is also observed that algorithm faults are more serious than assignment faults and checking faults. With relation to the question of which component in the target algorithms is associated with the highest risk, there is not enough evidence in this study to provide a definite answer. The study reveals that the three optimization algorithms exhibit similar trends in response to different faults. This is a key finding which supports, to a limited extent, the generalization of the findings of this study to other optimization algorithms at least for the two-dimensional bin packing problem. However, statistical analysis and more empirical studies using different optimization problems are required to provide a definite answer regarding the question whether all optimization algorithms behave similarly in the presence of the same fault distribution.