Add CN specs to MKM #142

podhrmic · 2024-12-02T23:17:21Z

This PR adds CN functional specifications to the MKM code in client.c, as well as various supporting files. These specifications are intended to be run-time tested as well as verified.

Files:

client.c - target function definitions
client.h - types, and CN predicates defining the types
cn_stubs.h - specifications and redefinitions for various library functions that can't be supported directly
run-cn-test.sh - run the CN test generator using the necessary flags
process-cn-test.sh - run the preprocessor. Called by run-cn-test.sh

Unfortunately, the CN verifier and test generators require different code-level annotations at various points. We handle this using a pair of macros:

CN_ENV - set when calling CN in either verify or test modes
CN_TEST - set when calling CN in test mode

Testing the PR

To run the verifier, run:

$ make cn_proof

Note this may be quite slow. It takes around 3m30s to complete on my newish MBP.

To run the tests, run:

$ ./run-cn-test.sh client.c test_directory

Outstanding bugs

The run-cn-test.sh script pauses during execution and only continues when I press return. I assume this is due to some call in client.c which is blocking, but I haven't figured out the culprit yet. FIXED
Various points in the code include TODO notes. These generally indicate places I'm working around a limitation in CN of some kind. But some of these might be possible to resolve.

Changes:

CN specs for memory safety
CN specs for functional correctness
Scripts for executing the run-time testing capabilities
Integration of proofs into CI
Integration of testing into CI
Fix bugs / limitations (see above)

components/mission_key_management/client-reduced.c

septract · 2024-12-31T23:59:24Z

@peterohanley @podhrmic PR ready to be re-reviewed when you have time. We now supports verification and functional correctness proofs of MKM, and testing of MKM. I've removed a lot of the limitations that existed before (but introduced some new ones caused by the test generator...).

peterohanley

The changes to failing malloc are big improvements.

spernsteiner · 2025-01-07T00:01:38Z

I tried this on Linux (running ./run-cn-test.sh client.c) and got an error about _IO_FILE:

In file included from ./client-gen_gen.h:6,
                 from ./client-gen_test.c:1:
./cn.h:18:8: error: redefinition of ‘struct _IO_FILE’
   18 | struct _IO_FILE {
      |        ^~~~~~~~
In file included from /usr/include/stdio.h:43,
                 from /home/spernsteiner/.opam/cn/lib/cn/runtime/include/cn-executable/utils.h:4,
                 from /home/spernsteiner/.opam/cn/lib/cn/runtime/include/cn-testing/alloc.h:6,
                 from /home/spernsteiner/.opam/cn/lib/cn/runtime/include/cn-testing/prelude.h:7,
                 from ./client-gen_gen.h:4:
/usr/include/x86_64-linux-gnu/bits/types/struct_FILE.h:49:8: note: originally defined here
   49 | struct _IO_FILE
      |        ^~~~~~~~

It seems like cn test copies the definition of struct _IO_FILE from our wars.h into a generated file cn.h, then includes both that file and the system-wide stdio.h, causing a conflict between the two definitions of struct _IO_FILE. However, just removing the definition from wars.h causes a CN error about struct _IO_FILE being undefined - CN's stdio.h mentions the struct via typedef struct _IO_FILE FILE;, but never defines it anywhere, thus triggering rems-project/cerberus#437.

I was able to work around this by patching MKM to not use stdio.h when building under CN, and then removing the definition of struct _IO_FILE from wars.h:

Click to see diff

diff --git a/components/include/wars.h b/components/include/wars.h
index f8f476c..81e230f 100644
--- a/components/include/wars.h
+++ b/components/include/wars.h
@@ -77,11 +77,4 @@
 // accepts this but CN rejects it
 #define WAR_CN_437 1
 
-#ifdef WAR_CN_437
-// this is required so we can mention FILE* parameters
-struct _IO_FILE {
-    int x;
-};
-#endif
-
 #endif // __CN_WARS_H__
diff --git a/components/mission_key_management/client.c b/components/mission_key_management/client.c
index f9e4426..71690d8 100644
--- a/components/mission_key_management/client.c
+++ b/components/mission_key_management/client.c
@@ -8,7 +8,6 @@
 
 #include <sys/socket.h>
 #include <unistd.h>
-#include <stdio.h>
 
 //SYSTEM_HEADERS
 // ^^^ magic string used during preprocessing - do not move / remove 
@@ -18,9 +17,12 @@
 #if ! defined(CN_ENV)
 # include <sys/types.h>
 # include <sys/epoll.h>
+# include <stdio.h>
+# define LOG(...)   (fprintf(stderr, __VA_ARGS__))
 #else  
 # include "cn_stubs.h"
 # include "cn_array_utils.h"
+# define LOG(...)   /* nothing */
 #endif
 
 // TODO `Alloc` construct not supported by `cn test`
@@ -445,11 +447,11 @@ $*/
                     c->response, c->response + MEASURE_SIZE);
             if (c->key == NULL) {
                 // No matching key was found for this request.
-                fprintf(stderr, "client %d: error: bad request for key %u\n", c->fd, c->key_id[0]);
+                LOG("client %d: error: bad request for key %u\n", c->fd, c->key_id[0]);
                 return RES_ERROR;
             }
             client_change_state(c, CS_SEND_KEY);
-            fprintf(stderr, "client %d: sending key %u\n", c->fd, c->key_id[0]);
+            LOG("client %d: sending key %u\n", c->fd, c->key_id[0]);
             break;
 
         case CS_SEND_KEY:
diff --git a/components/mission_key_management/cn_stubs.h b/components/mission_key_management/cn_stubs.h
index 17025ea..facafbd 100644
--- a/components/mission_key_management/cn_stubs.h
+++ b/components/mission_key_management/cn_stubs.h
@@ -80,10 +80,6 @@ $*/
 
 // From `stdio.h`
 
-/*$ spec fprintf(pointer f, pointer s);
-requires true;
-ensures true;
-$*/
 #if defined(CN_TEST)
 # define fprintf(...) 0 
 #endif 
@@ -129,14 +125,7 @@ $*/
 # define read(f,b,c) _read_uint8_t(f,b,c)
 #else 
 ssize_t _read_mock(void *buf, size_t count) {
-    // Fake file descriptor for use during testing 
-    FILE *file = tmpfile();
-    if (!file) {
-        perror("tmpfile failed (client_read)");
-        return -1;
-    }
-    int tmp_fd = fileno(file);
-    return read(tmp_fd, buf, count); 
+    return 0;
 }
 #define read(f,b,c) _read_mock(b,c)
 #endif 
@@ -155,14 +144,7 @@ $*/
 # define write(f,b,c) _write_uint8_t(f,b,c)
 #else 
 ssize_t _write_mock(const void *buf, size_t count) { 
-    // Fake file descriptor for use during testing 
-    FILE *file = tmpfile();
-    if (!file) {
-        perror("tmpfile failed (client_read)");
-        return -1;
-    }
-    int tmp_fd = fileno(file);
-    return write(tmp_fd, buf, count); 
+    return count;
 }
 #define write(f,b,c) _write_mock(b,c)
 #endif

podhrmic · 2025-01-07T01:19:38Z

@spernsteiner that is a good catch. We will need to add a CI job to run the test generation, which will probably show a couple of other issues.

podhrmic

Looks good! Minor comments above. Still need to add a CI job that runs the tests.
What do you think about linking the remaining TODOs to CN tickets, such that we known what needs to be fixed?

podhrmic · 2025-01-09T22:58:50Z

components/include/cn_array_utils.h

@@ -2,6 +2,18 @@
 #define CN_ARRAY_UTILS_H_

 /*$
+predicate (map<u64,u8>) Array_Owned_u8 (pointer p, u64 l) 


There is already a similar predicate - did you mean to use this one?

podhrmic · 2025-01-09T22:59:09Z

components/include/cn_array_utils.h

+  return Arr; 
+}
+
+predicate (map<u64,u8>) Array_Block_u8 (pointer p, u64 l) 


Same as above

podhrmic · 2025-01-09T23:01:11Z

components/include/cn_memory.h

@@ -69,4 +69,31 @@ ensures
    take i = each(u64 j; j >= 0u64 && j < n) {Block<uint8_t>(array_shift<uint8_t>(return, j))};
 $*/

+/*$
+datatype OptionMemory {


I would like to have at least a sentence of description for each predicate, similar to what Gus did for array_utils.h. I know this might be obvious to you, but this will really pay off during the transition. Maybe @peterohanley can help here?

podhrmic · 2025-01-09T23:02:35Z

components/mission_key_management/client.c

+# define NULL ((void *)0)
+#endif 
+
+/* TODO list: 


I am assuming you are still actively working on this TODO?
Also, this list should be a part of the PR description rather than being hidden in the code.

podhrmic · 2025-01-09T23:03:19Z

components/mission_key_management/client.c

+    SomeClientObject {struct client obj}, 
+    NoneClientObject {}
+}
+predicate (OptionClientObject) OptionClientNew(pointer p, i32 fd, i32 state)


Is it useful to have the predicates in a separate file?

podhrmic · 2025-01-09T23:04:56Z

components/mission_key_management/client.h

+// Pure predicate representing valid states of `enum client_state`. 
+// CN could easily generate this automatically (see #796) 
+/*$
+function (boolean) ValidState (u32 state) {


Thank you for the comments!

podhrmic · 2025-01-09T23:05:17Z

components/mission_key_management/client.h

+/* 
+    start:                  
+   ┌────────────────┐       
+┌─►│ CS_RECV_KEY_ID ├──────┐


Nice diagram!

podhrmic · 2025-01-09T23:06:01Z

components/mission_key_management/cn_stubs.h

+ensures true;
+$*/
+#if defined(CN_TEST)
+# define fprintf(...) 0 


All these should defines really be in some sort of CN standard library...

peterohanley reviewed Dec 4, 2024

View reviewed changes

components/mission_key_management/client-reduced.c Outdated Show resolved Hide resolved

spernsteiner force-pushed the 98-mkm-server branch from 5a2dcc7 to 0e65e31 Compare December 11, 2024 00:39

Base automatically changed from 98-mkm-server to main December 11, 2024 00:59

peterohanley mentioned this pull request Dec 11, 2024

Use shared OpenSUT CN definitions #144

Closed

peterohanley reviewed Dec 11, 2024

View reviewed changes

components/mission_key_management/client-reduced.c Outdated Show resolved Hide resolved

septract force-pushed the 139-feature-verify-test-mkm-module branch from 667e47c to a4f9a2a Compare December 18, 2024 21:56

add client-reduced, update cn_stubs

218a2f2

septract force-pushed the 139-feature-verify-test-mkm-module branch from a4f9a2a to 218a2f2 Compare December 18, 2024 22:42

septract added 14 commits December 18, 2024 18:00

Migrate CN memory safety specs into client.c

405d646

mkm: Prove memory safety for remaining fns

de0ba91

mkm: make proof use CN standard predicates

4f4b81e

mkm: handle array slices properly in read/write

f2cb2d9

Remove old test file client-reduced.c

c7f87d3

mkm: add state machine to client_event spec

093dd29

mkm: guard CN-specific ghost code with a macro

b7c4a19

mkm: clean up proof

faaa2ef

mkm: add script to split files, make client.h and others work with it

6fa262f

mkm: Add test script for cn test, modify other files to make it work

b50dd49

mkm: minor proof cleanup

6a59c43

mkm: make cn test work for most of the mkm fns

c520554

mkm: minor proof tidy up

adb30eb

mkm: made testing work with malloc / free fns, various cleanup

e0f081f

podhrmic linked an issue Dec 31, 2024 that may be closed by this pull request

[FEATURE] Verify / test MKM module #139

Open

4 tasks

septract requested a review from peterohanley December 31, 2024 23:56

mkm: integrated possibly-failing malloc()

8466469

septract mentioned this pull request Jan 1, 2025

Let malloc possibly fail #146

Closed

septract added 2 commits January 2, 2025 17:23

mkm: fix test demo pauses, support can-fail malloc in cn test flow

c44975b

mkm: test script now needs legacy --with-static-hack flag

59e7337

peterohanley approved these changes Jan 3, 2025

View reviewed changes

septract added 2 commits January 3, 2025 15:29

mkm: match Rust Option type naming

aa65423

mkm: use default in definitions (depends on cerberus PR #814)

a55fcb5

podhrmic closed this Jan 7, 2025

podhrmic reopened this Jan 7, 2025

mkm: initial work verifying policy.c

c8c7d93

podhrmic marked this pull request as ready for review January 9, 2025 22:57

podhrmic commented Jan 9, 2025

View reviewed changes

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Add CN specs to MKM #142

Add CN specs to MKM #142

podhrmic commented Dec 2, 2024 •

edited by septract

Loading

septract commented Dec 31, 2024

peterohanley left a comment

spernsteiner commented Jan 7, 2025

podhrmic commented Jan 7, 2025

podhrmic left a comment

podhrmic Jan 9, 2025

podhrmic Jan 9, 2025

podhrmic Jan 9, 2025

podhrmic Jan 9, 2025

podhrmic Jan 9, 2025

podhrmic Jan 9, 2025

podhrmic Jan 9, 2025

podhrmic Jan 9, 2025

Add CN specs to MKM #142

Are you sure you want to change the base?

Add CN specs to MKM #142

Conversation

podhrmic commented Dec 2, 2024 • edited by septract Loading

Testing the PR

Outstanding bugs

Changes:

septract commented Dec 31, 2024

peterohanley left a comment

Choose a reason for hiding this comment

spernsteiner commented Jan 7, 2025

podhrmic commented Jan 7, 2025

podhrmic left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

podhrmic commented Dec 2, 2024 •

edited by septract

Loading