Model-Agnostic and Efficient Exploration of Numerical Congestion Control State Space of Real-World TCP Implementations

• Published in: IEEE/ACM transactions on networking 2021-10, Vol.29 (5), p.1990-2004
• Main Authors: Sun, Wei, Xu, Lisong, Elbaum, Sebastian, Zhao, Di
• Format: Article
• Language: English
• Subjects: Aerospace electronics; Algorithms; Automation; Computer bugs; Congestion; Congestion control; Control algorithms; Control theory; Internet; Linux; Mathematical models; Numerical models; Parameters; random testing; Space exploration; state space; TCP (protocol); Testing
• ISSN: 1063-6692; 1558-2566
• DOI: 10.1109/TNET.2021.3078161

The significant impact of TCP congestion control on the Internet highlights the importance of testing congestion control algorithm implementations (CCAIs) in various network environments. Many CCAI testing problems can be solved by exploring the numerical state space of CCAIs, which is defined by a group of numerical (and nonnumerical) state variables of the CCAIs. However, the current practices for automated numerical state space exploration are either limited by the approximate abstract CCAI models or inefficient due to the large space of network environment parameters and the complicated relation between the CCAI states and network environment parameters. In this paper, we propose an automated numerical state space exploration method, called ACT, which leverages the model-agnostic feature of random testing and greatly improves its efficiency by guiding random testing under the feedback iteratively obtained in a test. Our experiments on five representative Linux TCP CCAIs show that ACT can more efficiently explore a large numerical state space than manual testing, undirected random testing, and symbolic execution based testing, while without requiring an abstract CCAI model. ACT detects multiple design and implementation bugs of these Linux TCP CCAIs, including some new bugs not reported before.