Skip to contentSkip to conversation

rbtree: Test against a verified oracle

PATCH In review Mete Polat 3 participants 7 messages Oct 19, 2021 – Oct 28, 2021 Library code

lore
Share & tools
lore

Mete Polat

author
#0 lore raw

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
author
#1 lore raw

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
index 3266fef7cb53..675c1a9fab67 100644
@@ -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
index b0cb89451cd3..8e563b959c60 100644
@@ -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
#2 lore raw

Re: [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

#3 lore raw

Re: [PATCH 1/2] rbtree: Expose a test tree to userspace

In reply to Mete Polat
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-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

author
#4 lore raw

PATCH 2/2 rbtree: add verified oracle with testing harness

In reply to Mete Polat

The 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
new file mode 100644
index 000000000000..cfe7d10d198f
@@ -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
new file mode 100644
index 000000000000..9a994af677b0
@@ -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
new file mode 100644
index 000000000000..f2e403d1dd8f
@@ -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
#5 lore raw
In reply to Mete Polat

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 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
author
#6 lore raw

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.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 ?

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.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 ?

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.c test 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 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