Pragmatic Random Sampling of the Linux Kernel: Enhancing the Randomness and Correctness of the conf Tool

Pragmatic Random Sampling of the Linux Kernel: Enhancing the Randomness and Correctness of the conf Tool David Fernandez-Amoros [email protected] Universidad Nacional de Educación a Distancia (UNED) Madrid, Spain Ruben Heradio [email protected] UNED Madrid, Spain Jose-Miguel Horcas [email protected] ITIS Software, Universidad de Málaga Málaga, Spain Jose A. Galindo [email protected] I3US, University of Seville Seville, Spain David Benavides [email protected] I3US, University of Seville Seville, Spain Lidia Fuentes [email protected] ITIS Software, Universidad de Málaga Málaga, Spain ABSTRACT The configuration space of some systems is so large that it cannot be computed. This is the case with the Linux Kernel , which provides almost 19,000 configurable options described across more than 1,600 files in the Kconfig language. As a result, many analyses of the Kernel rely on sampling its configuration space (e.g., debugging compilation errors, predicting configuration performance, finding the configuration that optimizes specific performance metrics, etc.). The Kernel can be sampled pragmatically, with its built-in tool conf , or idealistically, translating the Kconfig files into logic formulas. The pros of the idealistic approach are that it provides statistical guarantees for the sampled configurations, but the cons are that it sets out many challenging problems that have not been solved yet, such as scalability issues. This paper introduces a new version of conf called randconfig+ , which incorporates a series of improvements that increase the randomness and correctness of pragmatic sampling and also help validate the Boolean translation required for the idealistic approach. randconfig+ has been tested on 20,000 configurations generated for 10 different Kernel versions from 2003 to the present day. The experimental results show that randconfig+ is compatible with all tested Kernel versions, guarantees the correctness of the generated configurations, and increases conf’s randomness for numeric and string options. CCS CONCEPTS •Software and its engineering →Software product lines. KEYWORDS random sampling, configurable systems, variability modeling, software product lines, Kconfig, SAT, randconfig This work is licensed under a Creative Commons Attribution International 4.0 License. SPLC ’24, September 02–06, 2024, Dommeldange, Luxembourg ©2024 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-0593-9/24/09 https://doi.org/10.1145/3646548.3672586 ACM Reference Format: David Fernandez-Amoros, Ruben Heradio, Jose-Miguel Horcas, Jose A. Galindo, David Benavides, and Lidia Fuentes. 2024. Pragmatic Random Sampling of the Linux Kernel: Enhancing the Randomness and Correctness of the conf Tool. In 28th ACM International Systems and Software Product Line Conference (SPLC ’24), September 02–06, 2024, Dommeldange, Luxembourg. ACM, New York, NY, USA, 12 pages. https://doi.org/10.1145/3646548.3672586 1 INTRODUCTION Software systems are becoming increasingly customizable. One of the most outstanding examples is the Linux Kernel1 ( LK ), which provides thousands of configurable features to adjust to an extensive range of hardware devices. The importance of LK is considerable 2 , with a usage share of 69.94% on smartphones, 5.53% on desktop/laptop computers, and 100% on the top-500 most powerful supercomputers. LK ’s configurability is defined in a language named Kconfig3 . LK ’s configuration space is so vast that its valid configurations (i.e., the ones that conform to the Kconfig specification) cannot be enumerated. For instance, the most recent version of LK is v.6.8.4 and has 1,691 Kconfig files that specify 18,921 configurable options, known as configs, and their interdependencies. Accordingly, many relevant analyses on LK ’s configurability, which would be trivial if the configuration space could be enumerated, rely on working with configuration samples [ 29 , 30 , 37 ]. For example, the random sampling of LK has been used for (i) debugging compilation and building errors [ 27 , 28 , 36 , 52 ], (ii) accelerating configuration building times [ 39 ], (iii) predicting the performance of configurations [ 1 , 25 , 42 ], (iv) estimating the influence each option has on configurations’ performance [ 43 ], (v) finding the configuration that optimizes certain performance metrics [ 33 ], among others. A LK ’s configuration is stored in a file named .config . Generating a random .config file can be done through either the pragmatic or the idealistic approach, both of which are illustrated in Figure 1. (1) Pragmatic sampling uses the LK ’s built-in tool conf4 , which provides the following two options: 1Linux Kernel:https://www.kernel.org/ 2https://en.wikipedia.org/wiki/Usage_share_of_operating_systems 3Kconfig:https://www.kernel.org/doc/html/next/kbuild/kconfig-language.html 4conf is placed into the LK’s folder: ./scripts/kconfig 24 SPLC ’24, September 02–06, 2024, Dommeldange, Luxembourg Fernandez-Amoros, et al. Kconfig Boolean formula φ Solution of φ .config randconfig Kconfig to Boolean Translator Boolean to .config Translator Boolean Sampler   Figure 1: Two approaches to sample LK ’s configuration space --randconfig generates a random configuration. --oldconfig5 updates an existing configuration, repairing it if it does not fully meet the Kconfig specification. For conciseness, we will refer to conf together with its options --randconfig and --oldconfig , simply as randconfig and oldconfig. randconfig has the following limitations: • It is not random enough. For instance, when Acher et al. [ 1 ] generated 95,854 configurations for LK v4.13.3 , they found that randconfig often could not sufficiently diversify the values of some configs . Either the configs always got the same value, or they had an extremely unbalanced value distribution (e.g., 98% yes vs. 2% not for a Boolean config). • It may generate invalid configurations. For example, Section 4 reports an experiment where 563 out of 1,000 configurations generated with randconfig for LK v3.9.4 did not conform to the Kconfig specification. • It does not provide any theoretical guarantees. A crucial guarantee should be sampling uniformity, which is a statistical inference requirement to generalize sample findings to the population [ 20 , 38 ]. This property states that all configurations must have the same probability of being included in a sample. (2) Idealistic sampling pursues to overcome the limitations above. To do so, it performs the following steps depicted in Figure 1: • Step 1: Kconfig-to-Boolean translation. Translate the Kconfig files into a formal language, typically a Boolean formula 𝜑. •Step 2: Boolean sampling. Generate a random solution of 𝜑. • Step 3: Boolean-to-config translation. Translate back the formula solution into a .config file. Steps 1 and 2 are very challenging problems that have not been totally solved yet. • Step 1: Kconfig-to-Boolean translation. Despite the many attempts to translate Kconfig into Boolean logic [5, 10, 14, 23, 32, 44 , 50 , 51 ], none of them is complete (they do not fully adhere to Kconfig syntax), nor has been thoughtfully validated [ 12 , 14 ]. This is because the translation poses many difficulties. Firstly, it is necessary to clarify the semantics of Kconfig , given that 5 Later in this section, it will be shown that oldconfig usefulness is not for pragmatic sampling but to validate the translation of Kconfig into logic that idealistic sampling needs (see Figure 2). the official reference is only the Kconfig implementation itself. Although She and Berger [ 41 ] formalized some core aspects, its semantics still remain incomplete. Secondly, Kconfig includes non-Boolean options, such as configs of type tristate , numeric ( int and hex ), and string . Thirdly, Kconfig ’s configuration language is not fully declarative, but instead follows an imperative configuration mechanism where the order in which the options are selected alters the resulting config values. • Step 2: Boolean sampling. A number of algorithms have been proposed for generating random solutions for Boolean formulas [ 2 , 3 , 7 , 11 , 15 , 19 , 20 , 31 , 40 , 45 ]. However, none of them provide uniform sampling for very large systems like LK [15, 20, 38]. Despite its limitations, randconfig is widely used. For example, the 0-Day Test Service 6 , provided by Intel, reports performance and build tests on LK . Recently, Yildiran et al. [ 52 ] examined 36,115 of these reports from 2019 to 2022 7 . 65% of the configurations that were evaluated in the reports were randomly generated with randconfig . In other words, most of the analyses were possible thanks to randconfig . Section 2.1 reviews more randconfig usages described in the literature [1, 17, 24, 25, 27, 52]. randconfig and oldconfig are not only valuable by themselves but also to validate the Kconfig -to-Boolean translation that the idealistic approach requires. Let 𝐶Kconfig denote the set of valid configurations that conform to the Kconfig specification, and 𝐶𝜑 the set of valid solutions of the formula 𝜑 in which Kconfig is translated. To validate the translation, we should test whether 𝐶Kconfig =𝐶𝜑 or, more conveniently, 𝐶Kconfig ⊆𝐶𝜑 and 𝐶𝜑⊆𝐶Kconfig . However, as 𝐶Kconfig and 𝐶𝜑 are too big to be computed, the tests can only be performed experimentally with random sampling. Figure 2 sketches how to conduct these tests. Kconfig Boolean formula φ Solution of φ .config randconfig Boolean to .config Translator Boolean Sampler ⊆ φφ  Boolean assignment ω .config to Boolean Translator Boolean Engine .config oldconfig .config modified φΛω is SAT φΛω is not SAT φ ⊆  φ,  .config unmodified Figure 2: Validation schema (1) To test 𝐶Kconfig ⊆𝐶𝜑 , (i) generate as many configurations as possible with randconfig , (ii) translate each configuration to a Boolean assignment 𝜔 of 𝜑 , and (iii) check the satisfiability of 𝜑∧𝜔 with a Boolean engine (e.g., a SAT solver). If any of the 60-Day Test Service: https://01.org/lkp/documentation/0-day-test-service 7https://web.archive.org/web/20221023104058/https://lists.01.org/hyperkitty/ 25 Pragmatic Random Sampling of the Linux Kernel SPLC ’24, September 02–06, 2024, Dommeldange, Luxembourg configurations renders to be unsatisfiable, then the translation is invalid. (2) To test 𝐶𝜑⊆𝐶Kconfig , (i) generate as many solutions of 𝜑 as possible with a Boolean sampler [ 20 ], (ii) translate each solution into a .config file, and (iii) check with oldconfig whether the .config files need to be repaired. If any of them does, then the translation is invalid. In Section 2.3, we will see that (i) the 𝐶Kconfig ⊆𝐶𝜑 test was applied in the translation proposed in [ 14 ], and (ii) the translations described in [ 23 , 50 , 51 ] use a variation of the 𝐶𝜑⊆𝐶Kconfig test where, instead of sampling a Boolean formula that encodes the whole Kconfig system, it is used the set of all solutions that a formula encoding a miniature Kconfig excerpt has. This paper introduces a new version of conf called randconfig+ , which improves conf to overcome two of the three limitations of randconfig : its poor randomness and limited correctness. This benefits both LK sampling approaches. First, the quality of the samples obtained with the pragmatic approach increases. Second, the validity of any given translation from Kconfig to logic can be better assessed, hence boosting the achievement of the idealistic approach. The paper reports a randconfig+ validation on 20,000 random configurations generated for 10 LK versions spanning more than twenty years: from v.2.6.0 released in 2003 to the current v.6.8.4 . The empirical results show that, compared to conf , randconfig+ always ensures the generation of correct configurations for all the tested LK versions and increases the randomness of three of the five types of configs that Kconfig supports: int,hex, and string. The remainder of this paper is organized as follows: Section 2 reviews research on analyzing different aspects of LK through sampling, and procedures to validate the Kconfig -to-Boolean translation. Section 3 describes randconfig+ , pointing out its main improvements with respect to randconfig . Section 4 experimentally evaluates the benefits of these improvements. Finally, Section 5 summarizes the main conclusions of our work. 2 RELATED WORK Subsections 2.1 and 2.2 review the use of pragmatic and idealistic sampling for different purposes summarized in Table 1. Subsection 2.3 outlines several proposals to translate Kconfig into logic and their empirical validation. Table 1: Literature on solving LK problems through sampling Application Pragmatic Idealistic sampling sampling Analyzing compilation and building bugs [27] [28, 36] Accelerating configurations’ building [39] Detecting variability mismatches among [13] Kconfig,KBuild, and C preprocessor directives Predicting configuration performance [1, 25] [42] Estimating each config’s influence [43] on configuration performance Finding optimal configurations [33] Specializing configuration spaces [24] Fixing configuration conflicts [17] 2.1 Applications of Pragmatic Sampling 2.1.1 Analyzing compilation and building bugs. Melo et al. [ 27 ] analyzed compilation warnings in 21,030 configurations randomly generated with randconfig for the LK version 4.1.1. 2.1.2 Accelerating configuration building. To speed up building LK configurations, Randrianaina et al. [ 39 ] suggested doing it incrementally from previously compiled configurations instead of starting from scratch. To test their method, they generated configurations from LK with randconfig. 2.1.3 Predicting configuration performance. To create a performance model that estimates the size of the binary file resulting from building a LK configuration (i.e., its footprint [ 42 ]), Acher et al. [ 1 ] trained several machine learning algorithms on 95,854 configurations generated with randconfig from the kernel version 4.13.3. As tuning performance models is expensive in terms of time and data consumption, Martin et al. [ 25 ] proposed to reuse them as follows: imagine that a machine learning algorithm has already been trained for a given LK version. When a new version is released, instead of re-training a model again from scratch, update the pretrained model with a technique known as transfer learning. To evaluate their approach, Martin et al. used randconfig to generate thousands of configurations from the LK versions 4.13 , 4.15 , 4.20 , 5.0,5.4,5.7, and 5.8. 2.1.4 Specializing configuration spaces. Martin et al. [ 24 ] proposed a method for specializing a configuration space to achieve particular performance objectives. For instance, LK could be specialized to obtain a footprint below 50Mb by selecting/deselecting a set of options. To evaluate their procedure, Martin et al. reused the dataset provided in [1] and generated with randconfig. 2.1.5 Fixing configuration conflicts. Franz et al. [ 17 ] presented ConfigFix , a tool that automatically produces fixes for configuration conflicts in LK . To test ConfigFix , 27 configurations were generated with randconfig . Each configuration was later modified to include 50 conflicts that ConfigFix had to repair. 2.2 Applications of Idealistic Sampling 2.2.1 Analyzing compilation and building bugs. Although Kconfig was originated to manage LK ’s configurability, many other opensource projects have adopted it. Given the limitations of idealistic sampling, many works in the literature use these projects, considerably simpler than LK , as affordable substitutes. For example, Mordahl et al. [ 28 ] searched for building bugs in three miniature Kconfig systems: axTLS v.2.1.4 (94 features), Toybox v.0.7.5 (316 features), and BusyBox v1.28.0 (998 features). To do so, they translated their Kconfig specifications into logic with kclause8 [ 34 ] and examined random configurations generated with Smarch [ 35 ]. Oh et al. [ 36 ] extended Mordahl et al.’s work with the creation of kismet . Instead of dealing with a large formula for the whole Kconfig specification of LK , kismet works with small partial formulas for each select sentence and calls an SMT solver to check their satisfiability. 8kclause:https://github.com/jeho-oh/Kclause_Smarch 26 SPLC ’24, September 02–06, 2024, Dommeldange, Luxembourg Fernandez-Amoros, et al. 2.2.2 Detecting variability mismatches. LK ’s variability is specified with Kconfig and implemented through KBuild files and C preprocessor directives. Unfortunately, specification and implementation sometimes mismatches. El-Sharkawy et al. [ 13 ] proposed to detect these inconsistencies by translating everything into a Boolean formula, later examined with a SAT-solver. Kconfig files were translated with KconfigReader [ 23 ] , KBuild files with KbuildMiner9 and C preprocessor directives with Pilztaker10 . It is worth noting that, as next Section 2.3 discusses, none of these tools achieve a complete translation (i.e., one that encompasses all constructs of their source language). El-Sharkawy et al.’s approach was tested on LK v.4.4.1. 2.2.3 Predicting configuration performance. Sigmund et al. [ 42 ] proposed a method to construct performance models to predict configurations’ footprint. To test the method, they generated 100 configurations from a subset of LK composed of 25 features. They first translated by hand the original model subset into a Feature Model (FM) [ 21 ] that was then translated into logic. To generate a configuration from the formula, they randomly decided to select (or not) each feature, without considering the feature inter-dependencies. Then, the resulting feature selection was checked with SPLConqueror11 . When the selection was not valid, they started over. Note that this sampling approach only works in the simplest cases because the proportion of valid configurations (that satisfy the feature interdependencies) among all possible configurations is practically zero in most systems [ 20 ]. So, stumbling by chance with a valid configuration is almost impossible. 2.2.4 Estimating each config ’s influence on configuration performance. To analyze how features influence non-functional properties of the resulting configurations (e.g., performance, reliability, security, etc.), Sincero et al. [ 43 ] generated 146 random configurations from a miniature subset of LK focused on its scheduler. The sample was generated by manually translating the kernel subset into a FM, which was then converted into a logic formula encoded as a Binary Decision Diagram (BDD) [ 6 ]. The BDD was used to enumerate all valid configurations and, finally, the sample was randomly picked from the enumerated configurations. As stated in Section 1, configuration spaces are typically colossal, and thus they cannot be enumerated. Therefore, Sincero et al. ’s sampling approach does not work except for the smallest systems. 2.2.5 Finding optimal configurations. To assess different algorithms for finding configurations that optimize performance measures, Oh et al. [ 33 ] generated 46,250 configurations of axTLS v.2.1.4 y Toybox v.0.7.5 . The samples were produced by first converting the Kconfig specifications into a logic formula, and then processing the formula with the #SAT-based sampler Smarch. 2.3 Using conf to validate the Boolean translation of Kconfig As mentioned in Section 1, translating LK ’s Kconfig specification poses many challenges that have not been totally solved yet. 9KbuildMiner:https://github.com/ckaestne/KBuildMiner 10Pilztaker:https://github.com/SSE-LinuxAnalysis/pilztaker 11SPLConqueror:http://fosd.de/SPLConqueror She et al. [ 5 , 32 , 41 ] pioneered the translation, by setting the basis of Kconfig ’ formal definition and developing the LVAT tool, which is compatible with LK versions prior to 3.0 . Another longstanding tool is Undertaker by Tartler et al. [ 10 , 44 , 46 , 47 ], which, despite having the goal of detecting dead code blocks in LK ’s C implementation, it also provides programs for translating Kconfig into logic ( dumpconf+rsf2model in the first Undertaker versions, and satyr later). Neither LVAT nor Undertaker completely translate int , hex , and string configs [ 12 ]. Moreover, to the extent of our knowledge, the validation of these tools has not been reported in detail. Fernandez-Amoros et al. [ 14 ] presented Kconfig2Logic , which only considers Boolean configs . Kconfig2Logic was validated on the whole LK by testing 𝐶Kconfig ⊆𝐶𝜑 . Later, Fernandez-Amoros et al.[ 15 ] developed a more complete translation to (non-uniformly) sample LK configurations. This new translation was validated in both directions 𝐶Kconfig ⊆𝐶𝜑and 𝐶𝜑⊆𝐶Kconfig. Kästner [ 23 ] developed KconfigReader , which performs the most complete translation to date. KconfigReader was validated with a variation of the 𝐶𝜑⊆𝐶Kconfig schema in Figure 2. Instead of considering the whole LK ’s Kconfig specification, a test suite of mini Kconfig files was used, with up to 10 configs (86 test cases manually written by Kästner, 21 tests from LVAT , 32 tests from Undertaker , 15 tests from [ 12 ], and 100 randomly generated tests). Each test case was translated to a logic formula 𝜑 . Then, all solutions of 𝜑 were enumerated and translated to .config files, whose validity was checked back with oldconfig (i.e., a test case was considered to fail if oldconfig found necessary to repair the .config file). Recently, Yaman et al. [ 50 , 51 ] have proposed Kfeature , which translates Kconfig into FMs. Kfeature ’s validation is similar to KconfigReader ’s one, testing 𝐶𝜑⊆𝐶Kconfig by considering some miniature Kconfig files (the biggest one with 8 configs ). First, the tests were translated into FMs conforming to FeatureIDE12 XML schema [ 26 ]. Then, all valid configurations were enumerated with FeatureIDE . The validity of these configurations regarding the original Kconfig files was finally tested with Kmax13 . It is worth noting that Kfeature was validated against the complementary sets 𝐶′ 𝜑⊆𝐶′ Kconfig as well, i.e., testing that all invalid solutions in 𝜑correspond to invalid configurations in Kconfig. 3RANDCONFIG+: A CORRECT AND MORE RANDOM SAMPLER FOR LK This section points out the shortcomings of randconfig and explains the necessary changes and adaptions to overcome these limitations while including a very high-level explanation of Kconfig semantics. It is worth remarking that Kconfig is not only used in LK , but in many other open-source projects, such as axTLS14 , coreboot15 , etc. In contrast to relying on a consensus-based language such as UVL [ 4 ], every Kconfig -based system carries its own version of Kconfig , often involving lexical and syntactic differences. Even the 12FeatureIDE:https://featureide.github.io/ 13Kmax:https://github.com/paulgazz/kmax 14axTLS:https://axtls.sourceforge.net/ 15coreboot:https://www.coreboot.org 27 Pragmatic Random Sampling of the Linux Kernel SPLC ’24, September 02–06, 2024, Dommeldange, Luxembourg output format may differ; e.g., while it is customary to produce a .config file to be included in the main Makefile, axTLS produces a C header file. The LK does not suffer from a big fragmentation being just one project, but its long lifespan has introduced so many changes that adapting one tool to work with all versions is challenging. For example, when old LK versions encode a configuration into a .config file, all config values need to be specified. In contrast, the newer versions omit the configs without a prompt (i.e., configs that do not require user intervention). To provide the correct functioning, randconfig+ looks for the KERNELVERSION environment variable, which is defined in the LK Makefile to mimic the corresponding behavior. We believe supporting this compatibility is worthwhile because it allows longitudinal studies and differential analyses to be performed. A translation from Kconfig files to Boolean logic cannot be proven to be correct, as the Kconfig semantics are not formally defined, but it can be experimentally validated. As a part of the validation process, it would be necessary to generate random configurations and check if they are correct with respect to the translation. To improve the process, it would be beneficial to test it on multiple versions of the LK . Consider also a very hard problem, such as building a BDD for a LK translation to Boolean logic [ 15 ]. It may be more effective to try first with an older and smaller version, and then scale up the solution to the next ones, rather than starting with the latest version. Finally, machine learning approaches could also benefit from this abundance of versions, for instance, to predict feature evolution, which could be trained with old versions and tested using the latest versions. The LK versions considered in this work (see Section 4) span across more than twenty years, so the lexical and syntax analysis phases in randconfig+ have been modified to accommodate all the versions. In particular, the Kconfig language has evolved to allow new constructions, such as imply , arithmetic comparisons as a condition (e.g., if NR_CPUS < 8 ), and a macro subsystem that runs shell scripts to gather information about availability and versions of the toolchain and incorporates it in the configs . Overall, the more esoteric practices of the older syntax, such as allowing choices inside choices , have been forbidden in the modern LK versions, which produces cleaner semantics. Incorrect configurations can be discovered using oldconfig as an oracle; given a configuration file as input, oldconfig will correct the value of a config if it is wrong according to the Kconfig specification. So, it suffices to check if the configuration file has been modified to assess the validity of the configuration. If the file remains unchanged, the configuration is considered to be correct. However, if the configuration is found to be incorrect, oldconfig may still prompt the user for certain config values. Nevertheless, since we only require it to act as an oracle, we provide it with random inputs so the process can finish. We present here the basics of Kconfig , so the operation of the randconfig+ tool can be understood. The Kconfig language deals with five types of configs : bool , tristate , string , int and hex . The domain of bool values is { n , y }. Tristate configs domain is { n , m , y }. strings are just text strings, including the empty string. int and hex are integer numbers (coded in bases 10 and 16, respectively). There is also a choice construction, in which the user is asked to decide between different alternatives. The conf interpreter decides a suitable ordering of the configs and evaluates them in sequence. Kconfig constructions may constrain the acceptable values for a config based on the values of previously evaluated configs . For bool and tristate configs , some possible values may already be excluded because of previous choices. For int and hex configs , there is a range clause which may impose a lower and higher bound to the acceptable values. All configs may include conditional default clauses, in which a default value is specified if the condition holds. Evaluating a config will assign a value to the config . Most of the time, this involves asking the user for the value, in which case, the default value is used as a hint to the user. In other cases, the user is not asked, and the default value is assigned to the config . Kconfig is further discussed in the LK source tree in Documentation/kbuild/kconfig-language.rst. randconfig produces random configurations, but sometimes, they are invalid. The reason is that randconfig uses a specific function to produce the random configurations, instead of following the usual conf evaluation process with random inputs. Also, for types string , int and hex , randconfig only produces default values, specified by default clauses or a type-default value, (which is nothing for strings , and 0 for int and hex ). For this reason, even when the configurations created by randconfig are valid, they are expected to show a certain lack of variability. To solve all of these problems, we have customized conf to create randconfig+ . First, we analyze the Kconfig files to find the different string values mentioned in the code and to write them into a file we have called symbols . If a string config S contains a prompt to the user, a special value S_eq_OTHERVALUE is also added to express a value not mentioned anywhere in the Kconfig code. Then, the conf evaluation mechanism can proceed, but instead of asking the user, a random answer is assigned. For bool and tristate configs , the answer is chosen randomly among the permitted values. For strings , a value is chosen among the variants found in the symbols file. For int and hex , a random value is produced between the lower and higher bounds applicable, as explained later. These random answers are submitted to the same validity checks as in the original conf, so they are correct by construction. In this way, the randconfig+ tool produces valid configurations that exhibit more variability than the randconfig counterparts, as we will see in Section 4. In rare occasions, especially with integer constraints, it is not possible to get a valid answer, and the whole process has to be restarted. As an example, consider three integer configs : A , B , and C . Imagine that A and B are free to choose any value, but C has a range clause that says range A B , which means C has to be between A and B . If the value chosen for A is bigger than that of B , there is no possible value for C . Both tools, oldconfig and randconfig+ , will fail in this case, and the process will have to restart from the beginning after a few retries, as no backtracking capabilities are implemented. We now proceed to explain the changes specific to the different configuration types. 3.1 Logical config generation bool and tristate configs rely on trivalued logic. This logic allows the constants n , m , and y , variables, and the connectives && , 28 SPLC ’24, September 02–06, 2024, Dommeldange, Luxembourg Fernandez-Amoros, et al. || , and ! . Table 2 shows how to evaluate logic expressions to the values 0, 1, and 2. One of Kconfig main objectives is to model source file dependencies. A config often defines if and how a file is compiled 16 . If a file A.c , controlled by config A , can only be compiled in the presence of file B.c (e.g., because A.c calls a function defined in B.c ) controlled by config B , then one possibility is that A depends on B . Another possibility is that A selects B . Both alternatives support the same logical argument, but select forces B to be present, regardless of the user’s opinion and the dependencies of B . This latter feature of select is problematic, as it may confuse the user and also produce configurations that do not compile (because B ’s dependencies may be unmet). Changing select statements for the corresponding depends on is not always a solution, since that may introduce circular dependencies that cannot be managed by conf , e.g., config 𝐴1 depends on 𝐴2 , . . . , and 𝐴𝑛 depends on 𝐴1 . The imply construction was added to the language as an improvement over select . Unlike select , imply B will only change B if B ’s dependencies hold, and even then, the user may change B ’s value. To complicate things even further, if A.c is statically compiled in the Kernel (i.e., A=y ) and B.c is compiled as a module (i.e., B=m ), the compilation will fail because the Kernel is compiled and linked separately from the modules. Table 2: Evaluation rules for trivalued logic eval(n) =0 eval(m) =1 eval(y) =2 eval(expr1 && expr2) =mineval(expr1), eval(expr2) eval(expr1 || expr2) =maxeval(expr1), eval(expr2) eval(!expr) =2 - eval(expr) More formally, if a config , A , depends on an expression D , then eval(A) ≤eval(D) . If config S selects config T , then eval(S) ≤eval(T) . A conditional selection is also possible, so if config S selects T if C , then eval(S && C) ≤eval(T) . Select clauses are said to induce a reverse dependency. A config may have several depends on clauses, and several configs may select the same one. All the restrictions have to apply, so, if config A depends on 𝐷1, 𝐷2, . . . , 𝐷𝑛 and is selected conditionally by configs 𝑆1, 𝑆2, . . . , 𝑆𝑚with conditions 𝐶1, 𝐶2, . . . ,𝐶𝑛, then 𝑛 max 𝑖=1eval(𝑆𝑖&& 𝐶𝑖) ≤ eval(𝐴) ≤ 𝑚 min 𝑗=1𝐷𝑗 To produce a random value for logical configs , randconfig+ takes the values allowed by the dependencies and reverse dependencies (i.e., selects ), chooses randomly among them, and produces the answer instead of asking the user. oldconfig uses a special function for this effect, but sometimes produces wrong results. 3.2 string generation For string configs , we want to randomly choose among the possible values mentioned in the Kconfig code. If a string config S has a prompt or if the value can be obtained from an environment variable, we add another value; S_OTHERVAL , which represents a value 16n means the file is not compiled, y means the file will be compiled in the Kernel, m means the file will be compiled as a loadable module. different from any other one mentioned in the Kconfig code, so any test for equality against this value will fail. Including the name of the config in the value itself is very useful for further applications. For instance, suppose you want to compile the LK according to a generated configuration: The error “OTHERVALgcc not found” is not very informative, whereas “COMPILER_PREFIX_OTHERVALgcc not found” will point to the config that needs to be corrected. Detecting all the places in the syntactic analyzer where a string config value may appear is tricky. Furthermore, the default value for a string config may be another string config , and so on, as in Listing 1, taken from coreboot . We need a strategy to propagate the values from one string config to another. First, the parser must be modified to add the values in all the places where they can appear: • When a macro of type string is encountered, the OTHERVALUE value is added. • When an unknown symbol is compared to a string literal or a string symbol. • When a string config is compared with equality or inequality to a string literal. •When a prompt is found, the OTHERVALUE value is added. •When a default clause for a string config is found. • When the value for a string config is taken from an environment variable, the OTHERVALUE is added. Listing 1: A string whose value comes from another string 1config MAINBOARD_SMBIOS_PRODUCT_NAME 2prompt " SMBI OS Prod uct name " if 3!SMBIOS_PROVIDED_BY_MOBO 4string 5depends on GENERATE_SMBIOS_TABLES 6default MAINBOARD_PART_NUMBER 7help 8Override the Product name stored in SMBIOS structures Listing 2 shows the first case: A shell command is issued to determine the version of the bindgen tool, which is stored in string config BINDGEN_VERSION_TEXT. Listing 2: A string whose value comes from a macro 1config BINDGEN_VERSION_TEXT 2string 3depends on RUST 4default $( shell , command -v $( BINDGEN ) >/ dev / null 2 >&1 5&& $( BI NDG EN ) -- v ersion || echo n) An unknown symbol is a symbol for which the type is unknown for a while during parsing. This can happen if a config is defined without specifying a type but is redefined later with a type, or if a config is never declared in the current architecture (i.e., it is defined in another Kconfig file that is not included). Eventually, unknown symbols are resolved to string configs or the empty string. When parsing ends, it is time to propagate the string values as illustrated in Algorithm 1: Whenever a string config S takes values from another string config T , the possible values for T are computed (if they had not been computed already) and are propagated as values of S. The Kconfig code is analyzed once in this way, and the mapping of values for each string config is written into a file called symbols . randconfig+ simply reads the file and, if there is a prompt to ask for a string value, one of the possible values is randomly 29 Pragmatic Random Sampling of the Linux Kernel SPLC ’24, September 02–06, 2024, Dommeldange, Luxembourg picked. The configuration values end up as C preprocessor macros. It is outside the scope of this paper to analyze the C source files and obtain additional values for the string configs , but it would be an interesting extension. Algorithm 1 An algorithm to propagate string values function Propagate(related) ⊲related maps a symbol to a set of other symbols from which to take values for each symbol in related.keys() do ProcessSymbol(symbol, related) function ProcessSymbol(symbol, related) alreadyProcessed ← ∅ ⊲a set of symbols if symbol ∈alreadyProcessed then return insert symbol into alreadyProcessed for each other in related[symbol] do ProcessSymbol(other) for each value in other.values do insert value into symbol.values 3.3 int and hex generation For int and hex configs , there is a range construction in Kconfig to impose a lower and an upper bound. For instance, in Listing 3, the following range has to hold: 0≤SERIAL_82 - 50_RUNTIME_UARTS ≤SERIAL_8250_NR_UARTS . If there is a prompt to enter a value, randconfig+ chooses a random value between the lower and the upper bound. In the absence of a range clause, a random integer value is chosen and coded in the corresponding base. Listing 3 illustrates another problem: If the value of SERIAL_8250_RUNTIME_ - UARTS is negative, there is no possible value for SERIAL_8250_RUN - TIME_UARTS . In this case, a few attempts are made to try with different values for the configs in that menu, but ultimately, randconfig and randconfig+ may fail after several retries. The only mitigation would be to retry the whole configuration. randconfig always chooses the default values for int and hex configs , which causes it to miss interesting configurations, for instance: • The default values for NR_CPUS (i.e., the maximum number of CPUs) are selectable for many hardware architectures, but if config SMP (which stands for symmetric multiprocessing) is set, randconfig only produces configurations with an even number of CPUs, although odd numbers are allowed, meaning 50% of values are never produced. • The value of RCU_FANOUT has to be greater than or equal to 4 √NR_CPUS. •PHYSICAL_ALIGN can be entered by the user in architecture x86_32 , but it has to be between 0x2000 and 0x1000000, a power of 2, and bigger than or equal to MIN_KERNEL_ALIGN. The last two examples show some shortcomings of the Kconfig language. The constraints of these configs are verified in C source code, which seems reasonable since Kconfig is mainly focused on dealing with dependencies and logical constraints. Listing 3: Sample Kconfig snippet 1config SERIAL_CORE 2tristate 3config SERIAL_8250 4tristate " 8250/16550 and compatible serial support " 5select SERIAL_CORE 6help 7This selects whether you want to include the driver for 8the s tandard serial ports . 9config SERIAL_8250_NR_UARTS 10 int " Maximum number of 82 50/16550 serial ports " 11 depends on SERIAL_8250 12 default "4" 13 help 14 Set this to the number of serial ports you want the 15 driver to support . 16 config SERIAL_8250_RUNTIME_UARTS 17 int " Number of serial ports to register at runtime " 18 depends on SERIAL_8250 19 range 0 SERIAL_8250_NR_UARTS 20 default "4" 21 help 22 Set this to the maximum number of serial ports you 23 want the kernel to register at boot time . 4 EMPIRICAL EVALUATION This section reports the experimental validation we conducted to address the following three Research Questions (RQs): •RQ1: Randomness.Are the configurations generated with randconfig+ more random than those generated with randconfig ? • RQ2: Correctness.Do randconfig and randconfig+ ensure the generation of valid configurations? • RQ3: Time scalability.Is the time taken by randconfig+ to generate random configurations similar to that taken by randconfig? Table 3: LK versions considered in our experimental setup LK version #configs #Kconfig files LOCs 2.6.0 4,244 201 37,115 3.9.4 13,097 983 104,746 4.4.302 15,261 1,186 122,804 4.10.1 16,347 1,295 132,075 4.19.311 16,054 1,392 134,357 5.4.273 16,695 1,451 140,482 5.10.214 17,446 1,500 147,416 5.15.153 17,764 1,533 151,050 6.1.10 18,532 1,628 158,902 6.8.4 18,921 1,691 162,737 4.1 Experimental setup On an HP Proliant, with an Intel Xeon E5-2660v3 processor (2.6 GHz), 1,000 configurations were generated with randconfig and another 1,000 with randconfig+ for each of the ten LK versions summarized in Table 3 (i.e., 20,000 configurations in total, for the x86 architecture). The columns in Table 3 show the number of configs per version, the number of Kconfig files, and the total number of Lines Of Code (LOCs) of all Kconfig files, excluding comment and blank lines. 4.2 Results 4.2.1 RQ1: Randomness. For assessing the randomness of a configuration sample, two dimensions should be considered: the diversity 30 SPLC ’24, September 02–06, 2024, Dommeldange, Luxembourg Fernandez-Amoros, et al. Figure 3: Comparing the config entropies of the samples generated with randconfig and randconfig+ and the probability distribution of the config values. A metric that encompasses both perspectives and thus is widely used to measure randomness is entropy [9], from information theory. Given a config 𝑐 , which takes values in the set 𝑉 and is distributed in a configuration sample according to 𝑝 : 𝑉→ [ 0 , 1 ] , its entropy is calculated as: 𝐻(𝑐)=−∑︁ 𝑣∈𝑉 𝑝(𝑣) ·log2𝑝(𝑣) Entropy is always greater or equal to zero. The higher the entropy, the larger the randomness of the config values in the sample. Let us examine some examples to familiarize ourselves with the metric. Imagine a sample where: (1) A bool config always has the same value n. Its entropy is −𝑝(y)·log2𝑝(y)−𝑝(n)·log2𝑝(n)=− 0 ·log2 0 − 1 ·log2 1 = 0, which means “not random at all”. (2) A bool config that is y in 95% of the configurations, and n in the other 5%. Its entropy is − 0 . 95 ·log2 0 . 95 − 0 . 05 ·log2 0 . 05 = 0.29. (3) A bool config that is y in half the configurations. Its entropy is −0.5·log20.5−0.5·log20.5=1. (4) A tristate config that is y in 1 3 of the configurations, n in 1 3, and min 1 3. Its entropy is −3 3·log21 3=1.58. (2) has higher entropy than (1) because it is more diverse (two values instead of one). (3) has higher entropy than (2) because its probability distribution is more uniform; whereas in (2), it is almost sure the config will be y in a random configuration, in (3), any of the values, y or n , may likely happen. (4) has higher entropy than (3) because despite both having uniform probability distributions, the set of possible values of (4) is larger. Figure 3 compares, for each LK version, the config entropies of the samples generated with randconfig and randconfig+ . The figure follows the recommendations given in Chapter 12 of [ 49 ] to visualize differences between paired measurements. Each point represents a config , its 𝑥 and 𝑦 coordinates correspond to its entropies in the samples generated with randconfig and randconfig+ , respectively. A red diagonal line shows 𝑦=𝑥 . Two clusters of configs are distinguished with circled-blue and triangled-yellow points. Whereas the circled-blue points, that account for int , hex , and string configs , are shifted upwards relative to the diagonal line, the triangled-yellow points, that depict bool and tristate configs , are around the line. Accordingly, the randomness of the circledblue dots is higher for randconfig+ than for randconfig , but the triangled-yellow points show similar entropies for both samplers. Figure 4 focuses on the entropy differences. For each config , the difference between its entropy in the sample generated with randconfig+ minus its entropy in the randconfig ’s sample is calculated. Then, all differences are summarized with box plots 17 . While the bool and tristate box plots are around zero (Figure 4.b), the int , hex , and string box plots show a clear positive difference (Figure 4.a). Tables 4 and 5 summarize the entropy median and 95%-coverage interval 18 . The two last columns show the results of performing a Wilcoxon signed-rank test, which is a robust non-parametric test typically used to compare sets of paired-values (see Section 15.5 of [ 16 ] for a detailed justification of this test). In our case, the paired-values to test are the config entropies of randconfig vs. randconfig+ . Given the large sample size (1,000 configurations for randconfig plus another 1,000 for randconfig+ , i.e., 2,000 cases per test), all the tests are statistically significant (i.e., the summarized results are not due to chance). Whereas the effect sizes on bool and tristate configs are very small 19 (Table 4), the effect sizes on int,hex, and string are large (Table 5). 17 In a box plot, the thick central bar represents the median, the box contains the central half of the data, and the whiskers depict the lowest and highest values, excluding outliers (see Chapter 7 of [48]). 18 A 95%-coverage interval is widely used to describe the range of values in a sample. This interval includes all values except for the lowest 2.5% and the highest 2.5%. This helps to avoid any distortions that may be caused by extreme values. For more information, refer to Chapter 3 of [22]. 19 The effect size of Wilcoxon signed-rank tests is estimated with the 𝑟 statistic. The standard convention [ 8 ] is that when 𝑟< 0 . 3, the effect size is considered small, when 0.30 ≤𝑟<0.5, the effect is moderate, and when 𝑟≥0.5, the effect is large. 31 Pragmatic Random Sampling of the Linux Kernel SPLC ’24, September 02–06, 2024, Dommeldange, Luxembourg linux−2.6.0 linux−3.9.4 linux−4.4.302 linux−4.10.1 linux−4.19.311 linux−5.4.273 linux−5.10.214 linux−5.15.153 linux−6.1.10 linux−6.8.4 0.0 2.5 5.0 7.5 10.0 entropy differences ( randconfig+ − randconfig ) (a) int, hex & string configs linux−2.6.0 linux−3.9.4 linux−4.4.302 linux−4.10.1 linux−4.19.311 linux−5.4.273 linux−5.10.214 linux−5.15.153 linux−6.1.10 linux−6.8.4 −0.10 −0.05 0.00 0.05 0.10 entropy differences ( randconfig+ − randconfig ) (b) bool & tristate configs Figure 4: Entropy comparison Table 4: Statistical analysis of the randconfig and randconfig+entropies for bool and tristate configs randconfig randconfig+Wilcoxon LK entropy entropy signed-rank test version median 95% median 95% 𝑝-value effect coverage coverage size 2.6.0 1.45 [0, 1.57] 1.47 [0, 1.57] 3.8e-10 0.15 3.9.4 1.35 [0, 1.57] 1.40 [0, 1.57] 1.8e-13 0.09 4.4.302 1.44 [0, 1.58] 1.43 [0, 1.57] 1.2e-49 0.16 4.10.1 1.44 [0, 1.58] 1.43 [0, 1.57] 9.9e-47 0.15 4.19.311 1.44 [0, 1.58] 1.44 [0, 1.57] 1.6e-18 0.08 5.4.273 1.43 [0, 1.58] 1.44 [0, 1.57] 2.1e-28 0.10 5.10.214 1.46 [0, 1.58] 1.44 [0, 1.57] 2.8e-260 0.31 5.15.153 1.44 [0, 1.58] 1.44 [0, 1.57] 7.3e-49 0.13 6.1.10 1.44 [0, 1.58] 1.44 [0, 1.57] 1.8e-110 0.19 6.8.4 1.45 [0, 1.58] 1.46 [0, 1.57] 8.6e-21 0.08 Answer to RQ1: Randomness Regarding int , hex , and string configs , the configurations generated with randconfig+ are much more random than those generated with randconfig . Nevertheless, both are equivalent for bool and tristate configs. 4.2.2 RQ2: Correctness. As mentioned in Section 1, oldconfig is primarily intended to avoid configuring LK from scratch by updating old configurations specified in prior LK versions. In addition, it Table 5: Statistical analysis of the randconfig and randconfig+entropies for int,hex, and string configs randconfig randconfig+Wilcoxon LK entropy entropy signed-rank test version median 95% median 95% 𝑝-value effect coverage coverage size 2.6.0 0 [0, 0.42] 7.57 [3.17, 9.51] 1.8e-12 0.87 3.9.4 0 [0, 1.96] 5.95 [1.87, 9.15] 2.4e-25 0.86 4.4.302 0 [0, 1.88] 6.21 [1.85, 9.23] 3.1e-28 0.87 4.10.1 0 [0, 1.99] 6.19 [1.73, 9.26] 3.1e-29 0.87 4.19.311 0 [0, 2.01] 6.22 [1.72, 9.50] 5e-27 0.86 5.4.273 0 [0, 1.99] 6.08 [1.83, 9.63] 4.8e-28 0.87 5.10.214 0 [0, 2.05] 6.17 [1.98, 9.57] 1.6e-30 0.87 5.15.153 0 [0, 2.14] 6.17 [1.95, 9.50] 1.3e-31 0.87 6.1.10 0 [0, 2.05] 6.23 [1.89, 9.63] 1.7e-31 0.87 6.8.4 0 [0, 2.02] 5.55 [1.35, 9.56] 3e-34 0.86 can work as oracle to test if a configuration is invalid because oldconfig repairs the configurations that do not conform to the Kconfig specification. That is, any configuration is valid unless oldconfig modifies it. Figure 5 shows the results of checking the validity with oldconfig of the 20,000 sampled configurations. All the configurations that randconfig+ generated were valid for every LK version. In contrast, the first randconfig versions produced many invalid configurations (23.2% in LK v.2.6.0 , 60.8% in v.3.9.4 , 45.7% in v.4.4.302 , and 47.6% in v.4.10.1 ). Nevertheless, randconfig seems to work correctly since then. linux−2.6.0 linux−3.9.4 linux−4.4.302 linux−4.10.1 linux−4.19.311 linux−5.4.273 linux−5.10.214 linux−5.15.153 linux−6.1.10 linux−6.8.4 0 25 50 75 100 % of valid configurations sampler randconfig+ randconfig Figure 5: Percentage of valid configuration generated with randconfig+and randconfig Answer to RQ2: Correctness randconfig+ always generates valid configurations (at least, for the ten LK versions we examined). Before v4.19.311 , randconfig produced many invalid configurations. However, this problem has been fixed since then. 4.2.3 RQ3: Time scalability. Figure 6 shows the time in seconds randconfig+ and randconfig needed to generate 1,000 configurations for each LK version. Newer LK versions have higher complexity (see Table 3), and consequently, the samplers spent more time. 32