Merge pull request #64 from delcypher/overshift-fix

Overshift fixes

10 files changed, 315 insertions, 0 deletions

diff --git a/test/Feature/arithmetic-right-overshift-sym-conc.c b/test/Feature/arithmetic-right-overshift-sym-conc.c
new file mode 100644
index 00000000..81995b2b
--- /dev/null
+++ b/test/Feature/arithmetic-right-overshift-sym-conc.c
@@ -0,0 +1,65 @@
+// RUN: %llvmgcc %s -emit-llvm -g -O0 -c -o %t.bc
+// RUN: %klee -use-cex-cache=1 -check-overshift=0 %t.bc
+// RUN: not grep "ASSERTION FAIL" %T/klee-last/messages.txt
+// RUN: grep "KLEE: done: explored paths = 1" %T/klee-last/info
+#include <stdio.h>
+#include <assert.h>
+
+typedef enum
+{
+    TO_ZERO,
+    MASKED,
+    UNKNOWN
+} overshift_t;
+
+// We're using signed ints so should be doing
+// arithmetic right shift.
+int overshift(volatile unsigned int y, const char * type)
+{
+    overshift_t ret;
+    volatile signed int x=15;
+    unsigned int limit = sizeof(x)*8;
+
+    volatile signed int result;
+    result = x >> y; // Potential overshift
+
+    if (result ==0)
+    {
+        printf("%s : Overshift to zero\n", type);
+        ret = TO_ZERO;
+    }
+    else if (result == ( x >> (y % limit)) )
+    {
+        printf("%s : Bitmasked overshift\n", type);
+        ret = MASKED;
+    }
+    else
+    {
+        printf("%s : Unrecognised behaviour.\n", type);
+        ret = UNKNOWN;
+    }
+
+    return ret;
+}
+
+int main(int argc, char** argv)
+{
+    // Concrete overshift
+    volatile unsigned int y = sizeof(unsigned int)*8;
+    overshift_t conc = overshift(y, "Concrete");
+    assert( conc == TO_ZERO);
+
+    // Symbolic overshift
+    volatile unsigned int y2;
+    klee_make_symbolic(&y2,sizeof(y),"y2");
+    // Add constraints so only one value possible
+    klee_assume(y2 > (y-1));
+    klee_assume(y2 < (y+1));
+    overshift_t sym = overshift(y2, "Symbolic");
+    assert( sym == TO_ZERO);
+
+    // Concrete and symbolic behaviour should be the same
+    assert( conc == sym);
+
+    return 0;
+}
diff --git a/test/Feature/left-overshift-sym-conc.c b/test/Feature/left-overshift-sym-conc.c
new file mode 100644
index 00000000..e962fa28
--- /dev/null
+++ b/test/Feature/left-overshift-sym-conc.c
@@ -0,0 +1,63 @@
+// RUN: %llvmgcc %s -emit-llvm -g -O0 -c -o %t.bc
+// RUN: %klee -use-cex-cache=1 -check-overshift=0 %t.bc
+// RUN: not grep "ASSERTION FAIL" %T/klee-last/messages.txt
+// RUN: grep "KLEE: done: explored paths = 1" %T/klee-last/info
+#include <stdio.h>
+#include <assert.h>
+
+typedef enum
+{
+    TO_ZERO,
+    MASKED,
+    UNKNOWN
+} overshift_t;
+
+int overshift(volatile unsigned int y, const char * type)
+{
+    overshift_t ret;
+    volatile unsigned int x=15;
+    unsigned int limit = sizeof(x)*8;
+
+    volatile unsigned int result;
+    result = x << y; // Potential overshift
+
+    if (result ==0)
+    {
+        printf("%s : Overshift to zero\n", type);
+        ret = TO_ZERO;
+    }
+    else if (result == ( x << (y % limit)) )
+    {
+        printf("%s : Bitmasked overshift\n", type);
+        ret = MASKED;
+    }
+    else
+    {
+        printf("%s : Unrecognised behaviour.\n", type);
+        ret = UNKNOWN;
+    }
+
+    return ret;
+}
+
+int main(int argc, char** argv)
+{
+    // Concrete overshift
+    volatile unsigned int y = sizeof(unsigned int)*8;
+    overshift_t conc = overshift(y, "Concrete");
+    assert( conc == TO_ZERO);
+
+    // Symbolic overshift
+    volatile unsigned int y2;
+    klee_make_symbolic(&y2,sizeof(y),"y2");
+    // Add constraints so only one value possible
+    klee_assume(y2 > (y-1));
+    klee_assume(y2 < (y+1));
+    overshift_t sym = overshift(y2, "Symbolic");
+    assert( sym == TO_ZERO);
+
+    // Concrete and symbolic behaviour should be the same
+    assert( conc == sym);
+
+    return 0;
+}
diff --git a/test/Feature/logical-right-overshift-sym-conc.c b/test/Feature/logical-right-overshift-sym-conc.c
new file mode 100644
index 00000000..00281ec4
--- /dev/null
+++ b/test/Feature/logical-right-overshift-sym-conc.c
@@ -0,0 +1,65 @@
+// RUN: %llvmgcc %s -emit-llvm -g -O0 -c -o %t.bc
+// RUN: %klee -use-cex-cache=1 -check-overshift=0 %t.bc
+// RUN: not grep "ASSERTION FAIL" %T/klee-last/messages.txt
+// RUN: grep "KLEE: done: explored paths = 1" %T/klee-last/info
+#include <stdio.h>
+#include <assert.h>
+
+typedef enum
+{
+    TO_ZERO,
+    MASKED,
+    UNKNOWN
+} overshift_t;
+
+// We're using unsigned ints so should be doing
+// logical right shift.
+int overshift(volatile unsigned int y, const char * type)
+{
+    overshift_t ret;
+    volatile unsigned int x=15;
+    unsigned int limit = sizeof(x)*8;
+
+    volatile unsigned int result;
+    result = x >> y; // Potential overshift
+
+    if (result ==0)
+    {
+        printf("%s : Overshift to zero\n", type);
+        ret = TO_ZERO;
+    }
+    else if (result == ( x >> (y % limit)) )
+    {
+        printf("%s : Bitmasked overshift\n", type);
+        ret = MASKED;
+    }
+    else
+    {
+        printf("%s : Unrecognised behaviour.\n", type);
+        ret = UNKNOWN;
+    }
+
+    return ret;
+}
+
+int main(int argc, char** argv)
+{
+    // Concrete overshift
+    volatile unsigned int y = sizeof(unsigned int)*8;
+    overshift_t conc = overshift(y, "Concrete");
+    assert( conc == TO_ZERO);
+
+    // Symbolic overshift
+    volatile unsigned int y2;
+    klee_make_symbolic(&y2,sizeof(y),"y2");
+    // Add constraints so only one value possible
+    klee_assume(y2 > (y-1));
+    klee_assume(y2 < (y+1));
+    overshift_t sym = overshift(y2, "Symbolic");
+    assert( sym == TO_ZERO);
+
+    // Concrete and symbolic behaviour should be the same
+    assert( conc == sym);
+
+    return 0;
+}
diff --git a/test/Solver/lit.local.cfg b/test/Solver/lit.local.cfg
new file mode 100644
index 00000000..d64daf29
--- /dev/null
+++ b/test/Solver/lit.local.cfg
@@ -0,0 +1,2 @@
+# Look for .kquery files too
+config.suffixes.add('.kquery')
diff --git a/test/Solver/overshift-aright-by-constant.kquery b/test/Solver/overshift-aright-by-constant.kquery
new file mode 100644
index 00000000..c21889e2
--- /dev/null
+++ b/test/Solver/overshift-aright-by-constant.kquery
@@ -0,0 +1,14 @@
+# RUN: %kleaver %s > %t
+# RUN: not grep INVALID %t
+array x[4] : w32 -> w8 = symbolic
+# ∀ x. x > 0 → ( ((signed int) x) >> 32  = 0 )
+# Check we overshift to zero for when shifting for all 32-bit values >0
+
+(query [ (Ult  (w32 0) (ReadLSB w32 (w32 0) x)) ]
+    (Eq
+        (AShr w32
+            (ReadLSB w32 (w32 0) x)
+            (w32 32)
+        )
+        (w32 0)
+    ) [ ] [x] )
diff --git a/test/Solver/overshift-aright-by-symbolic.kquery b/test/Solver/overshift-aright-by-symbolic.kquery
new file mode 100644
index 00000000..af563ea3
--- /dev/null
+++ b/test/Solver/overshift-aright-by-symbolic.kquery
@@ -0,0 +1,26 @@
+# RUN: %kleaver %s > %t
+# RUN: not grep INVALID %t
+
+array shift[4] : w32 -> w8 = symbolic
+# ∀ x. x >= 32 → ( ( ( (signed int)2 ) >> x) = 0 )
+# Check we arithmetic right overshift to zero when shifting a constant ALWAYS!
+
+(query [ (Ule  (w32 32) (ReadLSB w32 (w32 0) shift)) ]
+    (Eq
+        (AShr w32 (w32 2)
+            (ReadLSB w32 (w32 0) shift)
+        )
+        (w32 0)
+    ) [ ] [shift] )
+
+# 64-bit version
+# ∀ x. x >= 64 → ( (((signed int) 2) >> x) = 0 )
+array shift64[8] : w32 -> w8 = symbolic
+
+(query [ (Ule  (w64 64) (ReadLSB w64 (w32 0) shift64)) ]
+    (Eq
+        (AShr w64 (w64 2)
+            (ReadLSB w64 (w32 0) shift64)
+        )
+        (w64 0)
+    ) [ ] [shift64] )
diff --git a/test/Solver/overshift-left-by-constant.kquery b/test/Solver/overshift-left-by-constant.kquery
new file mode 100644
index 00000000..e0709100
--- /dev/null
+++ b/test/Solver/overshift-left-by-constant.kquery
@@ -0,0 +1,14 @@
+# RUN: %kleaver %s > %t
+# RUN: not grep INVALID %t
+array x[4] : w32 -> w8 = symbolic
+# ∀ x. x > 0 → ( x << 32  = 0 )
+# Check we overshift to zero for when shifting for all 32-bit values >0
+
+(query [ (Ult  (w32 0) (ReadLSB w32 (w32 0) x)) ]
+    (Eq
+        (Shl w32
+            (ReadLSB w32 (w32 0) x)
+            (w32 32)
+        )
+        (w32 0)
+    ) [ ] [x] )
diff --git a/test/Solver/overshift-left-by-symbolic.kquery b/test/Solver/overshift-left-by-symbolic.kquery
new file mode 100644
index 00000000..9d0d272c
--- /dev/null
+++ b/test/Solver/overshift-left-by-symbolic.kquery
@@ -0,0 +1,26 @@
+# RUN: %kleaver %s > %t
+# RUN: not grep INVALID %t
+
+array shift[4] : w32 -> w8 = symbolic
+# ∀ x. x >= 32 → ( (2 << x) = 0 )
+# Check we left overshift to zero when shifting a constant ALWAYS!
+
+(query [ (Ule  (w32 32) (ReadLSB w32 (w32 0) shift)) ]
+    (Eq
+        (Shl w32 (w32 2)
+            (ReadLSB w32 (w32 0) shift)
+        )
+        (w32 0)
+    ) [ ] [shift] )
+
+# 64-bit version
+# ∀ x. x >= 64 → ( (2 << x) = 0 )
+array shift64[8] : w32 -> w8 = symbolic
+
+(query [ (Ule  (w64 64) (ReadLSB w64 (w32 0) shift64)) ]
+    (Eq
+        (Shl w64 (w64 2)
+            (ReadLSB w64 (w32 0) shift64)
+        )
+        (w64 0)
+    ) [ ] [shift64] )
diff --git a/test/Solver/overshift-lright-by-constant.kquery b/test/Solver/overshift-lright-by-constant.kquery
new file mode 100644
index 00000000..cb223dd5
--- /dev/null
+++ b/test/Solver/overshift-lright-by-constant.kquery
@@ -0,0 +1,14 @@
+# RUN: %kleaver %s > %t
+# RUN: not grep INVALID %t
+array x[4] : w32 -> w8 = symbolic
+# ∀ x. x > 0 → ( x >> 32  = 0 )
+# Check we overshift to zero for when shifting for all 32-bit values >0
+
+(query [ (Ult  (w32 0) (ReadLSB w32 (w32 0) x)) ]
+    (Eq
+        (LShr w32
+            (ReadLSB w32 (w32 0) x)
+            (w32 32)
+        )
+        (w32 0)
+    ) [ ] [x] )
diff --git a/test/Solver/overshift-lright-by-symbolic.kquery b/test/Solver/overshift-lright-by-symbolic.kquery
new file mode 100644
index 00000000..7ca6d4d5
--- /dev/null
+++ b/test/Solver/overshift-lright-by-symbolic.kquery
@@ -0,0 +1,26 @@
+# RUN: %kleaver %s > %t
+# RUN: not grep INVALID %t
+
+array shift[4] : w32 -> w8 = symbolic
+# ∀ x. x >= 32 → ( (2 >> x) = 0 )
+# Check we logical right overshift to zero when shifting a constant ALWAYS!
+
+(query [ (Ule  (w32 32) (ReadLSB w32 (w32 0) shift)) ]
+    (Eq
+        (LShr w32 (w32 2)
+            (ReadLSB w32 (w32 0) shift)
+        )
+        (w32 0)
+    ) [ ] [shift] )
+
+# 64-bit version
+# ∀ x. x >= 64 → ( (2 >> x) = 0 )
+array shift64[8] : w32 -> w8 = symbolic
+
+(query [ (Ule  (w64 64) (ReadLSB w64 (w32 0) shift64)) ]
+    (Eq
+        (LShr w64 (w64 2)
+            (ReadLSB w64 (w32 0) shift64)
+        )
+        (w64 0)
+    ) [ ] [shift64] )