rbtree: Test against a verified oracle
cover rbtree: Test against a verified oracle
Hi,
This patch series provides a pipeline for testing the kernel Red-Black tree implementation against a verified oracle and is based on the work which we presented on the LPC [1]. A verified oracle is an equivalent algorithm that is proven to be mathematically correct. The testing pipeline consists of a kernel module that exposes the core rbtree functions to userspace using debugfs, and a testing harness that implements two strategies to generate test cases which are then applied on the kernel rbtree and the verified rbtree (the oracle). After executing an operation on both versions, the harness checks if the kernel rbtree is valid by partially comparing it to the verified oracle.
See the second patch for a description of how to use the harness.
Some notes:
The verified rbtree was verified in the proof assistant Isabelle [2] and is written in a functional programming language. That's why I also wrote the testing harness in the functional programming Haskell.
I decided to not try to integrate this work into kselftests because
(1) Haskell (obviously) has another build system
(2) The tests can run several minutes and would just slow down the execution of all kselftests
There already is a decent rbtree testing module in the kernel. This work tries to address the issue of functional correctness using a more formal method and can be seen as an baseline for future (more complex) testing against verified oracles.
Regards,
Mete
[1] https://linuxplumbersconf.org/event/11/contributions/1036/
[2] https://isabelle.in.tum.de/
Mete Polat (2):
rbtree: Expose a test tree to userspace
rbtree: add verified oracle with testing harness
lib/Kconfig.debug | 19 ++ lib/Makefile | 1 + lib/test_rbtree_interface.c | 161 +++++++++++ tools/testing/rbtree_oracle/.gitignore | 1 + tools/testing/rbtree_oracle/Main.hs | 128 +++++++++ tools/testing/rbtree_oracle/RBT/Kernel.hs | 64 +++++ tools/testing/rbtree_oracle/RBT/Verified.hs | 253 ++++++++++++++++++ tools/testing/rbtree_oracle/RBT_export.thy | 41 +++ tools/testing/rbtree_oracle/Setup.hs | 2 + tools/testing/rbtree_oracle/Strategy.hs | 72 +++++ .../rbtree_oracle/rbtTestHarness.cabal | 15 ++ 11 files changed, 757 insertions(+) create mode 100644 lib/test_rbtree_interface.c create mode 100644 tools/testing/rbtree_oracle/.gitignore create mode 100644 tools/testing/rbtree_oracle/Main.hs create mode 100644 tools/testing/rbtree_oracle/RBT/Kernel.hs create mode 100644 tools/testing/rbtree_oracle/RBT/Verified.hs create mode 100644 tools/testing/rbtree_oracle/RBT_export.thy create mode 100644 tools/testing/rbtree_oracle/Setup.hs create mode 100644 tools/testing/rbtree_oracle/Strategy.hs create mode 100644 tools/testing/rbtree_oracle/rbtTestHarness.cabal
Signature · 1 line
2.33.1
PATCH 1/2 rbtree: Expose a test tree to userspace
Expose rbtree manipulation functions on debugfs. These can be used for testing the core rbtree implementation from userspace against a verified oracle (a mathematically proven correct Red-Black tree):
<debugfs>/rbt_if/cmd
write:
0 = Reset rbtree (remove all nodes).
1 = Insert key (see other file) into rbtree.
2 = Delete key (see other file) from rbtree.
read:
Print tree.
<debugfs>/rbt_if/key
Read or write the key used for cmds
--- lib/Kconfig.debug | 19 +++++ lib/Makefile | 1 + lib/test_rbtree_interface.c | 161 ++++++++++++++++++++++++++++++++++++ 3 files changed, 181 insertions(+) create mode 100644 lib/test_rbtree_interface.c
lib/Kconfig.debug +19 -0
@@ -2623,6 +2623,25 @@ config TEST_CLOCKSOURCE_WATCHDOG If unsure, say N. +config TEST_RBTREE_INTERFACE + tristate "Expose an Red-Black tree instance to userspace for testing" + depends on DEBUG_FS + help + Exposes rbtree maniplation functions on debugfs. These can be used for + testing the core rbtree implementation from userspace against a + verified oracle (a mathematically proven correct Red-Black tree): + <debugfs>/rbt_if/cmd + write: + 0 = Reset rbtree (remove all nodes). + 1 = Insert key (see other file) into rbtree. + 2 = Delete key (see other file) from rbtree. + read: + Print tree. + <debugfs>/rbt_if/key + Read or write the key used for cmds + + If unsure, say N. + endif # RUNTIME_TESTING_MENU config ARCH_USE_MEMTEST
lib/Makefile +1 -0
@@ -100,6 +100,7 @@ obj-$(CONFIG_TEST_MEMINIT) += test_meminit.o obj-$(CONFIG_TEST_LOCKUP) += test_lockup.o obj-$(CONFIG_TEST_HMM) += test_hmm.o obj-$(CONFIG_TEST_FREE_PAGES) += test_free_pages.o +obj-$(CONFIG_TEST_RBTREE_INTERFACE) += test_rbtree_interface.o # # CFLAGS for compiling floating point code inside the kernel. x86/Makefile turns
lib/test_rbtree_interface.c new file +161 -0
161 lines not on this page · raw message
Signature · 1 line
2.33.1
kernel test robot
build botRe: [PATCH 1/2] rbtree: Expose a test tree to userspace
Thank you for the patch! Perhaps something to improve:
Hi Mete,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on linus/master]
[also build test WARNING on v5.15-rc6 next-20211019]
[If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]
url: https://github.com/0day-ci/linux/commits/Mete-Polat/rbtree-Test-against-a-verified-oracle/20211019-171711 base: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git 519d81956ee277b4419c723adfb154603c2565ba config: hexagon-randconfig-r033-20211019 (attached as .config) compiler: clang version 14.0.0 (https://github.com/llvm/llvm-project b37efed957ed0a0193d80020aefd55cb587dfc1f)
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# https://github.com/0day-ci/linux/commit/d73723d42ad47ca335de00e899a9e94b03d8b57d
git remote add linux-review https://github.com/0day-ci/linux
git fetch --no-tags linux-review Mete-Polat/rbtree-Test-against-a-verified-oracle/20211019-171711 git checkout d73723d42ad47ca335de00e899a9e94b03d8b57d
# save the attached .config to linux build tree
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 ARCH=hexagon
If you fix the issue, kindly add following tag as appropriate
All warnings (new ones prefixed by >>):
>> lib/test_rbtree_interface.c:91:9: warning: no previous prototype for function 'cmd_exec' [-Wmissing-prototypes]
ssize_t cmd_exec(struct file *file, const char __user *ubuf, size_t len, loff_t *offp)
^
lib/test_rbtree_interface.c:91:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
ssize_t cmd_exec(struct file *file, const char __user *ubuf, size_t len, loff_t *offp)
^
static
>> lib/test_rbtree_interface.c:138:12: warning: no previous prototype for function 'rbt_if_init' [-Wmissing-prototypes]
int __init rbt_if_init(void)
^
lib/test_rbtree_interface.c:138:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
int __init rbt_if_init(void)
^
static
>> lib/test_rbtree_interface.c:149:13: warning: no previous prototype for function 'rbt_if_exit' [-Wmissing-prototypes]
void __exit rbt_if_exit(void)
^ lib/test_rbtree_interface.c:149:1: note: declare 'static' if the function is not intended to be used outside of this translation unit void __exit rbt_if_exit(void)
^
static
3 warnings generated.
vim +/cmd_exec +91 lib/test_rbtree_interface.c
90
> 91 ssize_t cmd_exec(struct file *file, const char __user *ubuf, size_t len, loff_t *offp)
92 {
93 int cmd;
94 struct data *data, *_n;
95 struct rb_node *node;
96 int ret = kstrtoint_from_user(ubuf, len, 10, &cmd);
97 if (ret)
98 return ret;
99
100 switch (cmd) {
101 case RESET:
102 rbtree_postorder_for_each_entry_safe(data, _n, &rbt, node)
103 kfree(data);
104 rbt = RB_ROOT;
105 break;
106 case INSERT:
107 data = kzalloc(sizeof(*data), GFP_KERNEL);
108 data->key = input_key;
109 rb_find_add(&data->node, &rbt, node_cmp);
110 break;
111 case DELETE:
112 node = rb_find(&input_key, &rbt, key_cmp);
113 if (!node)
114 break;
115 rb_erase(node, &rbt);
116 kfree(data_from_node(node));
117 break;
118 default:
119 return -EINVAL;
120 }
121 return len;
122 }
123
124 static int cmd_open(struct inode *inode, struct file *file)
125 {
126 return single_open(file, cmd_show, inode->i_private);
127 }
128
129 static const struct file_operations cmd_fops = {
130 .owner = THIS_MODULE,
131 .open = cmd_open,
132 .read = seq_read,
133 .write = cmd_exec,
134 .llseek = seq_lseek,
135 .release = single_release,
136 };
137
> 138 int __init rbt_if_init(void)
139 {
140 rbt_if_root = debugfs_create_dir("rbt_if", NULL);
141 if (IS_ERR(rbt_if_root))
142 return PTR_ERR(rbt_if_root);
143
144 debugfs_create_file("cmd", 0644, rbt_if_root, NULL, &cmd_fops);
145 debugfs_create_u64("key", 0644, rbt_if_root, &input_key);
146 return 0;
147 }
148
> 149 void __exit rbt_if_exit(void) 150 {
151 struct data *_n, *pos;
152 debugfs_remove_recursive(rbt_if_root);
153 rbtree_postorder_for_each_entry_safe(pos, _n, &rbt, node)
154 kfree(pos);
155
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org
kernel test robot
build botRe: [PATCH 1/2] rbtree: Expose a test tree to userspace
In reply to Mete PolatThank you for the patch! Perhaps something to improve:
Hi Mete,
Thank you for the patch! Perhaps something to improve:
[auto build test WARNING on linus/master]
[also build test WARNING on v5.15-rc6 next-20211021]
[If your patch is applied to the wrong git tree, kindly drop us a note. And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch]
url: https://github.com/0day-ci/linux/commits/Mete-Polat/rbtree-Test-against-a-verified-oracle/20211019-171711 base: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git 519d81956ee277b4419c723adfb154603c2565ba config: nds32-randconfig-r032-20211019 (attached as .config) compiler: nds32le-linux-gcc (GCC) 11.2.0
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# https://github.com/0day-ci/linux/commit/d73723d42ad47ca335de00e899a9e94b03d8b57d
git remote add linux-review https://github.com/0day-ci/linux
git fetch --no-tags linux-review Mete-Polat/rbtree-Test-against-a-verified-oracle/20211019-171711 git checkout d73723d42ad47ca335de00e899a9e94b03d8b57d
# save the attached .config to linux build tree
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=gcc-11.2.0 make.cross ARCH=nds32
If you fix the issue, kindly add following tag as appropriate
All warnings (new ones prefixed by >>):
>> lib/test_rbtree_interface.c:91:9: warning: no previous prototype for 'cmd_exec' [-Wmissing-prototypes]
91 | ssize_t cmd_exec(struct file *file, const char __user *ubuf, size_t len, loff_t *offp)
| ^~~~~~~~
>> lib/test_rbtree_interface.c:138:12: warning: no previous prototype for 'rbt_if_init' [-Wmissing-prototypes]
138 | int __init rbt_if_init(void)
| ^~~~~~~~~~~
>> lib/test_rbtree_interface.c:149:13: warning: no previous prototype for 'rbt_if_exit' [-Wmissing-prototypes]
149 | void __exit rbt_if_exit(void)
| ^~~~~~~~~~~vim +/cmd_exec +91 lib/test_rbtree_interface.c
90
> 91 ssize_t cmd_exec(struct file *file, const char __user *ubuf, size_t len, loff_t *offp)
92 {
93 int cmd;
94 struct data *data, *_n;
95 struct rb_node *node;
96 int ret = kstrtoint_from_user(ubuf, len, 10, &cmd);
97 if (ret)
98 return ret;
99
100 switch (cmd) {
101 case RESET:
102 rbtree_postorder_for_each_entry_safe(data, _n, &rbt, node)
103 kfree(data);
104 rbt = RB_ROOT;
105 break;
106 case INSERT:
107 data = kzalloc(sizeof(*data), GFP_KERNEL);
108 data->key = input_key;
109 rb_find_add(&data->node, &rbt, node_cmp);
110 break;
111 case DELETE:
112 node = rb_find(&input_key, &rbt, key_cmp);
113 if (!node)
114 break;
115 rb_erase(node, &rbt);
116 kfree(data_from_node(node));
117 break;
118 default:
119 return -EINVAL;
120 }
121 return len;
122 }
123
124 static int cmd_open(struct inode *inode, struct file *file)
125 {
126 return single_open(file, cmd_show, inode->i_private);
127 }
128
129 static const struct file_operations cmd_fops = {
130 .owner = THIS_MODULE,
131 .open = cmd_open,
132 .read = seq_read,
133 .write = cmd_exec,
134 .llseek = seq_lseek,
135 .release = single_release,
136 };
137
> 138 int __init rbt_if_init(void)
139 {
140 rbt_if_root = debugfs_create_dir("rbt_if", NULL);
141 if (IS_ERR(rbt_if_root))
142 return PTR_ERR(rbt_if_root);
143
144 debugfs_create_file("cmd", 0644, rbt_if_root, NULL, &cmd_fops);
145 debugfs_create_u64("key", 0644, rbt_if_root, &input_key);
146 return 0;
147 }
148
> 149 void __exit rbt_if_exit(void) 150 {
151 struct data *_n, *pos;
152 debugfs_remove_recursive(rbt_if_root);
153 rbtree_postorder_for_each_entry_safe(pos, _n, &rbt, node)
154 kfree(pos);
155
---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org
PATCH 2/2 rbtree: add verified oracle with testing harness
In reply to Mete PolatThe folder rbtree_oracle hosts a Haskell project that consists of:
- the verified Haskell RBT implementation (RBT/Verified.hs)
- a Haskell interface to communicate to the kernel module that exposes some rbtree operations (RBT/Kernel.hs)
- two different test strategies (Strategy.hs) which propose test cases that are then applied on the oracle (the verified implementation RBT/Verified.hs) and on the kernel rbt using the kernel module interface.
- a entry point for the executable (Main.hs) which also compares the kernel and verified rbtree after executing a test case
- an Isabelle (the proof assistant in which the verified RBT was formalized and proved) export file to export the proved RBT implementation to Haskell (RBT/Verified.hs; requires Isabelle to export).
- files to build the Haskell project with cabal (a build system for Haskell)
The whole test suite is in the functional programming language Haskell because the verified RBT (the oracle) is also written in a functional language (Isabelle/HOL).
Use 'cabal run rbtTestHarness -- <OPTIONS>' to build and run the test harness with the specified options. This requires the GHC Haskell compiler and the Haskell cabal build system.
$ cabal run --verbose=0 rbtTestHarness -- --help Testing harness for comparing the Linux Red-Black trees against a verified oracle. The harness immediately stops when a kernel RBT violates an RBT invariant and prints an error message.
Usage: rbtTestHarness [-v] COMMAND
Available options:
-v Print all executed operations and the
resulting trees.
-h,--help Show this help text
Available commands:
random Randomly call insert and delete operations on
the kernel and oracle without resetting their trees. Will lead to large trees.
exhaustive Try (almost) all combinations up to a limit.
$ cabal run --verbose=0 rbtTestHarness -- random --help Usage: rbtTestHarness random -n ARG [-s <seed>] Randomly call insert and delete operations on the kernel and oracle without resetting their trees. Will lead to large trees.
Available options:
-s <seed> Seed for the pseudo-random-number generator
(default: 42)
-h,--help Show this help text
$ cabal run --verbose=0 rbtTestHarness -- exhaustive --help Usage: rbtTestHarness exhaustive -n ARG Try (almost) all combinations up to a limit.
Available options:
-h,--help Show this help text
--- tools/testing/rbtree_oracle/.gitignore | 1 + tools/testing/rbtree_oracle/Main.hs | 128 +++++++++ tools/testing/rbtree_oracle/RBT/Kernel.hs | 64 +++++ tools/testing/rbtree_oracle/RBT/Verified.hs | 253 ++++++++++++++++++ tools/testing/rbtree_oracle/RBT_export.thy | 41 +++ tools/testing/rbtree_oracle/Setup.hs | 2 + tools/testing/rbtree_oracle/Strategy.hs | 72 +++++ .../rbtree_oracle/rbtTestHarness.cabal | 15 ++ 8 files changed, 576 insertions(+) create mode 100644 tools/testing/rbtree_oracle/.gitignore create mode 100644 tools/testing/rbtree_oracle/Main.hs create mode 100644 tools/testing/rbtree_oracle/RBT/Kernel.hs create mode 100644 tools/testing/rbtree_oracle/RBT/Verified.hs create mode 100644 tools/testing/rbtree_oracle/RBT_export.thy create mode 100644 tools/testing/rbtree_oracle/Setup.hs create mode 100644 tools/testing/rbtree_oracle/Strategy.hs create mode 100644 tools/testing/rbtree_oracle/rbtTestHarness.cabal
tools/testing/rbtree_oracle/.gitignore new file +1 -0
@@ -0,0 +1 @@ +dist-*
tools/testing/rbtree_oracle/Main.hs new file +128 -0
128 lines not on this page · raw message
tools/testing/rbtree_oracle/RBT/Kernel.hs new file +64 -0
64 lines not on this page · raw message
tools/testing/rbtree_oracle/RBT/Verified.hs new file +253 -0
253 lines not on this page · raw message
tools/testing/rbtree_oracle/RBT_export.thy new file +41 -0
41 lines not on this page · raw message
tools/testing/rbtree_oracle/Setup.hs new file +2 -0
@@ -0,0 +1,2 @@ +import Distribution.Simple +main = defaultMain
tools/testing/rbtree_oracle/Strategy.hs new file +72 -0
72 lines not on this page · raw message
tools/testing/rbtree_oracle/rbtTestHarness.cabal new file +15 -0
@@ -0,0 +1,15 @@ +cabal-version: 2.4 +name: rbtTestHarness +version: 1.0.0.0 + +executable rbtTestHarness + main-is: Main.hs + other-modules: Strategy RBT.Kernel RBT.Verified + build-depends: base ^>=4.15, + random, + optparse-applicative, + extra, + mtl + default-language: Haskell2010 + default-extensions: RecordWildCards, DuplicateRecordFields + license: GPL-2.0
Signature · 1 line
2.33.1
Hi Mete,
I have two questions regarding the approach:
- Has it been considered to compare the tools/lib/rbtree.c library against the oracle, instead of the lib/rbtree.c one, so that the test can run fully in userspace ? The two versions closely follow each other, is there a worry that results would vary between them ?
- lib/rbtree_test.c has code that validates the rbtree invariants (i.e. that all leaf paths have the same black_path_count, etc); is that significantly weaker than comparing the rbtree shape against the oracle ? My worry here is that, if one were to update the rbtree code in ways that preserve the design invariants, but result in a different tree shape, they would now have to reflect those changes into the oracle, which may be difficult if they are not too familiar with haskel ?
(if validating rbtree invariants makes sense, it might still be useful to extend the lib/rbtree_test.c test case generator to cover more than random test cases, as you have done in your proposal...)
Thanks,
Quoted 67 lines · Mete Polat
Hi,
This patch series provides a pipeline for testing the kernel Red-Black tree implementation against a verified oracle and is based on the work which we presented on the LPC [1]. A verified oracle is an equivalent algorithm that is proven to be mathematically correct. The testing pipeline consists of a kernel module that exposes the core rbtree functions to userspace using debugfs, and a testing harness that implements two strategies to generate test cases which are then applied on the kernel rbtree and the verified rbtree (the oracle). After executing an operation on both versions, the harness checks if the kernel rbtree is valid by partially comparing it to the verified oracle.
See the second patch for a description of how to use the harness.
Some notes:
The verified rbtree was verified in the proof assistant Isabelle [2] and is written in a functional programming language. That's why I also wrote the testing harness in the functional programming Haskell.
I decided to not try to integrate this work into kselftests because
(1) Haskell (obviously) has another build system
(2) The tests can run several minutes and would just slow down the execution of all kselftestsThere already is a decent rbtree testing module in the kernel. This work tries to address the issue of functional correctness using a more formal method and can be seen as an baseline for future (more complex) testing against verified oracles.
Regards,
Mete
[1] https://linuxplumbersconf.org/event/11/contributions/1036/
[2] https://isabelle.in.tum.de/Mete Polat (2):
rbtree: Expose a test tree to userspace
rbtree: add verified oracle with testing harnesslib/Kconfig.debug | 19 ++ lib/Makefile | 1 + lib/test_rbtree_interface.c | 161 +++++++++++ tools/testing/rbtree_oracle/.gitignore | 1 + tools/testing/rbtree_oracle/Main.hs | 128 +++++++++ tools/testing/rbtree_oracle/RBT/Kernel.hs | 64 +++++ tools/testing/rbtree_oracle/RBT/Verified.hs | 253 ++++++++++++++++++ tools/testing/rbtree_oracle/RBT_export.thy | 41 +++ tools/testing/rbtree_oracle/Setup.hs | 2 + tools/testing/rbtree_oracle/Strategy.hs | 72 +++++ .../rbtree_oracle/rbtTestHarness.cabal | 15 ++ 11 files changed, 757 insertions(+) create mode 100644 lib/test_rbtree_interface.c create mode 100644 tools/testing/rbtree_oracle/.gitignore create mode 100644 tools/testing/rbtree_oracle/Main.hs create mode 100644 tools/testing/rbtree_oracle/RBT/Kernel.hs create mode 100644 tools/testing/rbtree_oracle/RBT/Verified.hs create mode 100644 tools/testing/rbtree_oracle/RBT_export.thy create mode 100644 tools/testing/rbtree_oracle/Setup.hs create mode 100644 tools/testing/rbtree_oracle/Strategy.hs create mode 100644 tools/testing/rbtree_oracle/rbtTestHarness.cabalSignature · 1 line
2.33.1
Hi, Michel,
Quoted 8 lines · Michel Lespinasse
Hi Mete,
I have two questions regarding the approach:
- Has it been considered to compare the
tools/lib/rbtree.clibrary against the oracle, instead of thelib/rbtree.cone, so that the test can run fully in userspace ? The two versions closely follow each other, is there a worry that results would vary between them ?
No I have not considered that, mainly because I wanted to explore what steps are necessary to test real in-kernel functionality against a verified oracle and present an example testing pipeline here.
Quoted 9 lines
-
lib/rbtree_test.chas code that validates the rbtree invariants (i.e. that all leaf paths have the sameblack_path_count, etc); is that significantly weaker than comparing the rbtree shape against the oracle ? My worry here is that, if one were to update the rbtree code in ways that preserve the design invariants, but result in a different tree shape, they would now have to reflect those changes into the oracle, which may be difficult if they are not too familiar with haskel ?
The Haskell code also just checks if the kernel rbtrees satisfy the invariants. While I originally also implemented the option to compare the shape of the trees, I removed it again because there does not exist a formal proof for the kernel rbtree delete algorithm yet and the Haskell variant indeed differs from the kernel one. Currently the verified oracle is then just used to check if the inorder of kernel and verified trees equal but one could also check if the shapes equal when just inserting nodes.
In general, one advantage of comparing shapes instead of checking invariants is that the former one is faster for bigger inputs. However, (in my opinion) checking invariants as lib/rbtree_test is doing is at least as strong as comparing shapes from the correctness point of view.
Quoted 4 lines
(if validating rbtree invariants makes sense, it might still be useful to extend the
lib/rbtree_test.ctest case generator to cover more than random test cases, as you have done in your proposal...)
This could be a good compromise. An exhaustive (but scoped) test case generator like in the Haskell code would be a nice extension.
Regards,
Mete
Quoted 71 lines
Thanks,
Quoted 67 lines · Mete Polat
Hi,
This patch series provides a pipeline for testing the kernel Red-Black tree implementation against a verified oracle and is based on the work which we presented on the LPC [1]. A verified oracle is an equivalent algorithm that is proven to be mathematically correct. The testing pipeline consists of a kernel module that exposes the core rbtree functions to userspace using debugfs, and a testing harness that implements two strategies to generate test cases which are then applied on the kernel rbtree and the verified rbtree (the oracle). After executing an operation on both versions, the harness checks if the kernel rbtree is valid by partially comparing it to the verified oracle.
See the second patch for a description of how to use the harness.
Some notes:
The verified rbtree was verified in the proof assistant Isabelle [2] and is written in a functional programming language. That's why I also wrote the testing harness in the functional programming Haskell.
I decided to not try to integrate this work into kselftests because
(1) Haskell (obviously) has another build system
(2) The tests can run several minutes and would just slow down the execution of all kselftestsThere already is a decent rbtree testing module in the kernel. This work tries to address the issue of functional correctness using a more formal method and can be seen as an baseline for future (more complex) testing against verified oracles.
Regards,
Mete
[1] https://linuxplumbersconf.org/event/11/contributions/1036/
[2] https://isabelle.in.tum.de/Mete Polat (2):
rbtree: Expose a test tree to userspace
rbtree: add verified oracle with testing harnesslib/Kconfig.debug | 19 ++ lib/Makefile | 1 + lib/test_rbtree_interface.c | 161 +++++++++++ tools/testing/rbtree_oracle/.gitignore | 1 + tools/testing/rbtree_oracle/Main.hs | 128 +++++++++ tools/testing/rbtree_oracle/RBT/Kernel.hs | 64 +++++ tools/testing/rbtree_oracle/RBT/Verified.hs | 253 ++++++++++++++++++ tools/testing/rbtree_oracle/RBT_export.thy | 41 +++ tools/testing/rbtree_oracle/Setup.hs | 2 + tools/testing/rbtree_oracle/Strategy.hs | 72 +++++ .../rbtree_oracle/rbtTestHarness.cabal | 15 ++ 11 files changed, 757 insertions(+) create mode 100644 lib/test_rbtree_interface.c create mode 100644 tools/testing/rbtree_oracle/.gitignore create mode 100644 tools/testing/rbtree_oracle/Main.hs create mode 100644 tools/testing/rbtree_oracle/RBT/Kernel.hs create mode 100644 tools/testing/rbtree_oracle/RBT/Verified.hs create mode 100644 tools/testing/rbtree_oracle/RBT_export.thy create mode 100644 tools/testing/rbtree_oracle/Setup.hs create mode 100644 tools/testing/rbtree_oracle/Strategy.hs create mode 100644 tools/testing/rbtree_oracle/rbtTestHarness.cabalSignature · 1 line
2.33.1