From 015245caabb16c3898fac68a9ab218ec681d53a4 Mon Sep 17 00:00:00 2001 From: jihoonl Date: Wed, 8 Jul 2009 00:02:47 +0000 Subject: [PATCH] Intruder final --- .../src/Benchmarks/SingleTM/Intruder/Arg.java | 9 +- .../SingleTM/Intruder/Detector.java | 218 ++++- .../SingleTM/Intruder/Dictionary.java | 123 +-- .../Benchmarks/SingleTM/Intruder/Node.java | 93 +-- .../Benchmarks/SingleTM/Intruder/Packet.java | 6 +- .../SingleTM/Intruder/Preprocessor.java | 31 +- .../Benchmarks/SingleTM/Intruder/RBTree.java | 782 ++++++++++++++++-- .../Benchmarks/SingleTM/Intruder/Stream.java | 140 ++-- 8 files changed, 1073 insertions(+), 329 deletions(-) diff --git a/Robust/src/Benchmarks/SingleTM/Intruder/Arg.java b/Robust/src/Benchmarks/SingleTM/Intruder/Arg.java index 8312c440..5a426091 100644 --- a/Robust/src/Benchmarks/SingleTM/Intruder/Arg.java +++ b/Robust/src/Benchmarks/SingleTM/Intruder/Arg.java @@ -1,2 +1,9 @@ -public class Args { +public class Arg { + /* input: */ + Stream streamPtr; + Decoder decoderPtr; + // output : + Vector_t[] errorVectors; + + public Arg() {} } diff --git a/Robust/src/Benchmarks/SingleTM/Intruder/Detector.java b/Robust/src/Benchmarks/SingleTM/Intruder/Detector.java index defc7c1c..4f1c6f0a 100644 --- a/Robust/src/Benchmarks/SingleTM/Intruder/Detector.java +++ b/Robust/src/Benchmarks/SingleTM/Intruder/Detector.java @@ -1,43 +1,187 @@ +/* ============================================================================= + * + * detector.java + * + * ============================================================================= + * + * Copyright (C) Stanford University, 2006. All Rights Reserved. + * Author: Chi Cao Minh + * + * ============================================================================= + * + * For the license of bayes/sort.h and bayes/sort.c, please see the header + * of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of kmeans, please see kmeans/LICENSE.kmeans + * + * ------------------------------------------------------------------------ + * + * For the license of ssca2, please see ssca2/COPYRIGHT + * + * ------------------------------------------------------------------------ + * + * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the + * header of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of lib/rbtree.h and lib/rbtree.c, please see + * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree + * + * ------------------------------------------------------------------------ + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford University nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + * + * ============================================================================= + */ + + public class Detector { - Dictionary dictionaryPtr; - Vector_t preprocessorVectorPtr; - - public Detector() { - dictionaryPtr = new Dictionary(); - if (dictionaryPtr == null) { - System.out.printString("Error: Cannot allocate Dictionary"); - System.exit(0); - } - preprocessorVectorPtr = new Vector_t(1); - if (preprocessorVectorPtr == null) { - System.out.printString("Error: Cannot allocate preprocessorVectorPtr"); - System.exit(0); - } - } - - public void detector_addPreprocessor(String p) - { - boolean status = preprocessorVectorPtr.vector_pushBack(p); - if (status == false) { - System.out.print("Error: Cannot insert in vector\n"); - System.exit(0); + + Dictionary dictionaryPtr; + Vector_t preprocessorVectorPtr; + + public Detector() {} + +/* ============================================================================= + * detector_alloc + * ============================================================================= + detector_t* detector_alloc (); + */ + public static Detector alloc() { + Detector detectorPtr = new Detector(); + + if(detectorPtr != null) { + detectorPtr.dictionaryPtr = new Dictionary(); + if(detectorPtr.dictionaryPtr == null) { + System.out.println("Assertion in Detector.alloc"); + System.exit(1); + } + + detectorPtr.preprocessorVectorPtr = Vector_t.vector_alloc(1); + if(detectorPtr.preprocessorVectorPtr == null) { + System.out.println("Assertion in Detector.alloc"); + System.exit(1); + } + } + + return detectorPtr; } - } - - public boolean detector_process(String str) - { - Vector_t v = this.preprocessorVectorPtr; - int p; - int numPreprocessor = v.vector_getSize(); - for (p = 0; p < numPreprocessor; p++) { - String preprocessor = (String) v.vector_at(p); - String newstr = p.toLowerCase(); + +/* ============================================================================= + * Pdetector_alloc + * ============================================================================= + detector_t* Pdetector_alloc (); + */ + + +/* ============================================================================= + * detector_free + * ============================================================================= + void detector_free (detector_t* detectorPtr); + */ + + +/* ============================================================================= + * Pdetector_free + * ============================================================================= + void Pdetector_free (detector_t* detectorPtr); + */ + + +/* ============================================================================= + * detector_addPreprocessor + * ============================================================================= + void detector_addPreprocessor (detector_t* detectorPtr, preprocessor_t p); + */ + public void addPreprocessor(int p) { + boolean status = preprocessorVectorPtr.vector_pushBack(new Integer(p)); + if(!status) { + System.out.println("Assertion in Detector.addPreprocessor"); + System.exit(1); + } } - String signature = dictionaryPtr.dictionary_match(str); - if (signature == null) { - return ERROR_SIGNATURE; + +/* ============================================================================= + * detector_process + * ============================================================================= + * error_t detector_process (detector_t* detectorPtr, char* str); + */ + public int process(String str) + { + /* + * Apply preprocessors + */ + + int p; + int numPreprocessor = preprocessorVectorPtr.vector_getSize(); + for(p = 0; p < numPreprocessor; p++) { + Integer preprocessor = (Integer)preprocessorVectorPtr.vector_at(p); + if(preprocessor.intValue() == 1) { + convertURNHex.process(str); + System.out.println("NOOOOOOOOOOOOO"); + } + else if(preprocessor.intValue() == 2) { + str = str.toLowerCase(); + } + else { + System.out.println("NOOOOOOOOOOOOO"); + } + } + + /* + * Check against signatures of known attacks + */ + + ERROR err = new ERROR(); +// System.out.print("str = \"" + str+ "\""); + String signature = dictionaryPtr.match(str); +// System.out.println("\tSign = \"" + signature+ "\""); + if(signature != null) { + return err.SIGNATURE; + } + + return err.NONE; } - return ERROR_NONE; - } } + +/* ============================================================================= + * + * End of detector.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Intruder/Dictionary.java b/Robust/src/Benchmarks/SingleTM/Intruder/Dictionary.java index cfdb353a..2ea45a75 100644 --- a/Robust/src/Benchmarks/SingleTM/Intruder/Dictionary.java +++ b/Robust/src/Benchmarks/SingleTM/Intruder/Dictionary.java @@ -1,9 +1,10 @@ public class Dictionary { String global_defaultSignatures[]; - long global_numDefaultSignature = 72; + int global_numDefaultSignature; public Dictionary() { - global_defaultSignatures = new String[72]; + global_numDefaultSignature = 71; + global_defaultSignatures = new String[71]; global_defaultSignatures[0] = "about"; global_defaultSignatures[1] = "after"; @@ -24,73 +25,75 @@ public class Dictionary { global_defaultSignatures[16] = "from"; global_defaultSignatures[17] = "get"; global_defaultSignatures[18] = "give"; - global_defaultSignatures[20] = "good"; - global_defaultSignatures[21] = "have"; - global_defaultSignatures[22] = "him"; - global_defaultSignatures[23] = "how"; - global_defaultSignatures[24] = "into"; - global_defaultSignatures[25] = "its"; - global_defaultSignatures[26] = "just"; - global_defaultSignatures[27] = "know"; - global_defaultSignatures[28] = "like"; - global_defaultSignatures[29] = "look"; - global_defaultSignatures[30] = "make"; - global_defaultSignatures[31] = "most"; - global_defaultSignatures[32] = "new"; - global_defaultSignatures[33] = "not"; - global_defaultSignatures[34] = "now"; - global_defaultSignatures[35] = "one"; - global_defaultSignatures[36] = "only"; - global_defaultSignatures[37] = "other"; - global_defaultSignatures[38] = "out"; - global_defaultSignatures[39] = "over"; - global_defaultSignatures[40] = "people"; - global_defaultSignatures[41] = "say"; - global_defaultSignatures[42] = "see"; - global_defaultSignatures[43] = "she"; - global_defaultSignatures[44] = "some"; - global_defaultSignatures[45] = "take"; - global_defaultSignatures[46] = "than"; - global_defaultSignatures[47] = "that"; - global_defaultSignatures[48] = "their"; - global_defaultSignatures[49] = "them"; - global_defaultSignatures[50] = "then"; - global_defaultSignatures[51] = "there"; - global_defaultSignatures[52] = "these"; - global_defaultSignatures[53] = "they"; - global_defaultSignatures[54] = "think"; - global_defaultSignatures[55] = "this"; - global_defaultSignatures[56] = "time"; - global_defaultSignatures[57] = "two"; - global_defaultSignatures[58] = "use"; - global_defaultSignatures[59] = "want"; - global_defaultSignatures[60] = "way"; - global_defaultSignatures[61] = "well"; - global_defaultSignatures[62] = "what"; - global_defaultSignatures[63] = "when"; - global_defaultSignatures[64] = "which"; - global_defaultSignatures[65] = "who"; - global_defaultSignatures[66] = "will"; - global_defaultSignatures[67] = "with"; - global_defaultSignatures[68] = "work"; - global_defaultSignatures[69] = "would"; - global_defaultSignatures[70] = "year"; - global_defaultSignatures[71] = "your" + global_defaultSignatures[19] = "good"; + global_defaultSignatures[20] = "have"; + global_defaultSignatures[21] = "him"; + global_defaultSignatures[22] = "how"; + global_defaultSignatures[23] = "into"; + global_defaultSignatures[24] = "its"; + global_defaultSignatures[25] = "just"; + global_defaultSignatures[26] = "know"; + global_defaultSignatures[27] = "like"; + global_defaultSignatures[28] = "look"; + global_defaultSignatures[29] = "make"; + global_defaultSignatures[30] = "most"; + global_defaultSignatures[31] = "new"; + global_defaultSignatures[32] = "not"; + global_defaultSignatures[33] = "now"; + global_defaultSignatures[34] = "one"; + global_defaultSignatures[35] = "only"; + global_defaultSignatures[36] = "other"; + global_defaultSignatures[37] = "out"; + global_defaultSignatures[38] = "over"; + global_defaultSignatures[39] = "people"; + global_defaultSignatures[40] = "say"; + global_defaultSignatures[41] = "see"; + global_defaultSignatures[42] = "she"; + global_defaultSignatures[43] = "some"; + global_defaultSignatures[44] = "take"; + global_defaultSignatures[45] = "than"; + global_defaultSignatures[46] = "that"; + global_defaultSignatures[47] = "their"; + global_defaultSignatures[48] = "them"; + global_defaultSignatures[49] = "then"; + global_defaultSignatures[50] = "there"; + global_defaultSignatures[51] = "these"; + global_defaultSignatures[52] = "they"; + global_defaultSignatures[53] = "think"; + global_defaultSignatures[54] = "this"; + global_defaultSignatures[55] = "time"; + global_defaultSignatures[56] = "two"; + global_defaultSignatures[57] = "use"; + global_defaultSignatures[58] = "want"; + global_defaultSignatures[59] = "way"; + global_defaultSignatures[60] = "well"; + global_defaultSignatures[61] = "what"; + global_defaultSignatures[62] = "when"; + global_defaultSignatures[63] = "which"; + global_defaultSignatures[64] = "who"; + global_defaultSignatures[65] = "will"; + global_defaultSignatures[66] = "with"; + global_defaultSignatures[67] = "work"; + global_defaultSignatures[68] = "would"; + global_defaultSignatures[69] = "year"; + global_defaultSignatures[70] = "your"; } - String dictionary_get(long i) { + public String get(int i) { if (i < 0 || i >= global_numDefaultSignature) { System.out.print("dictionary_get: Index out of bounds"); } return global_defaultSignatures[i]; } - String dictionary_match(String str) { - long i; - - for (i = 0; i < global_defaultSignatures; i++) { + public String match(String str) { + int i; + +// System.out.println("str= " + str); + for (i = 0; i < global_numDefaultSignature; i++) { + // System.out.println("global_numDefaultSignature= " + global_numDefaultSignature + " str= " + str + " global_defaultSignatures[" +i+"]= " + global_defaultSignatures[i]); if(global_defaultSignatures[i].equals(str)) { - return global_defaultSignatures[i]; + return str; } } return null; diff --git a/Robust/src/Benchmarks/SingleTM/Intruder/Node.java b/Robust/src/Benchmarks/SingleTM/Intruder/Node.java index 13a87167..8e02de9f 100644 --- a/Robust/src/Benchmarks/SingleTM/Intruder/Node.java +++ b/Robust/src/Benchmarks/SingleTM/Intruder/Node.java @@ -1,90 +1,13 @@ -#define LDA(a) a -#define STA(a,v) a = v -#define LDV(a) a -#define STV(a,v) a = v -#define LDF(o,f) o.f -#define STF(o,f,v) o.f = v -#define LDNODE(o,f) LDF(o,f) - -#define RED 0 -#define BLACK 1 - -#define SUCCESSOR(n) sucessor(n) -#define PARENT_OF(n) parentOf(n) -#define LEFT_OF(n) leftOf(n) -#define RIGHT_OF(n) rightOf(n) -#define COLOR_OF(n) colorOf(n) -#define SET_COLOR(n, c) setColor(n, c) public class Node { - int k; - Object v; - RBTree p; - RBTree l; - RBTree r; - int c; - - public Node() { } - - public Node parentOf(Node n) { - if (n != null) { - return LDNODE(n,p); - } - return null; - } - - public Node leftOf(Node n) { - if (n != null) { - return LDNODE(n, l); - } - return null; - } - - public Node rightOf(Node n) { - if (n != null) { - return LDNODE(n, r); - } - return null; - } - - public int colorOf(Node n) { - if (n != null) { - return LDNODE(n, c); - } - return BLACK; - } - - public void setColor(Node n, int c) { - if (n != null) { - STF(n, c, c); - } - } - - /* - * Return the given node's successor node---the node which has the - * next key in the the left to right ordering. If the node has - * no successor, a null pointer is returned rather than a pointer to - * the nil node - */ - public Node successor(Node t) { - if (t == null) { - return null; - } else if (LDNODE(t, r) != null) { - Node p = LDNODE(t, r); - while (LDNODE(p, l) != null) { - p = LDNODE(p, l); - } - return p; - } else { - Node p = LDNODE(t, p); - Node ch = t; - while (p != NULL && ch == LDNODE(p, r)) { - ch = p; - p = LDNODE(p, p); - } - return p; - } - } + int k; // key + Object v; // val + Node p; // parent + Node l; // left + Node r; // right + int c; // color + + public Node() {} } diff --git a/Robust/src/Benchmarks/SingleTM/Intruder/Packet.java b/Robust/src/Benchmarks/SingleTM/Intruder/Packet.java index da555179..e8723532 100644 --- a/Robust/src/Benchmarks/SingleTM/Intruder/Packet.java +++ b/Robust/src/Benchmarks/SingleTM/Intruder/Packet.java @@ -7,16 +7,16 @@ public class Packet { public Packet(int numDataBytes) { - char c[] = new char[numDataByte]; + char c[] = new char[numDataBytes]; data = new String(c); } - public long packet_compareFlowID(Packet aPtr, Packet bPtr) + public static int compareFlowID(Packet aPtr, Packet bPtr) { return aPtr.flowId - bPtr.flowId; } - public long packet_compareFragmentID(Packet aPtr, Packet bPtr) + public static int compareFragmentID(Packet aPtr, Packet bPtr) { return aPtr.fragmentId - bPtr.fragmentId; } diff --git a/Robust/src/Benchmarks/SingleTM/Intruder/Preprocessor.java b/Robust/src/Benchmarks/SingleTM/Intruder/Preprocessor.java index 89c989a6..fbb1f2b3 100644 --- a/Robust/src/Benchmarks/SingleTM/Intruder/Preprocessor.java +++ b/Robust/src/Benchmarks/SingleTM/Intruder/Preprocessor.java @@ -1,15 +1,30 @@ public class Preprocessor { public Preprocessor() {} - public void preprocessor_convertURNHex(char str[]) - { - System.out.printString("Error: preprocessor_convertURNHex not implemented\n"); - System.exit(0); - return; + public void process(String str) { + } - public String preprocessor_toLower(String str) - { - return str.toLowerCase(); + + /* + public static void main(String[] argv) { + + System.out.println("Starting..."); + + String hex = new String("This%20is %41 test%3F%3f"); + + Preprocessor.convertURNHex(hex); + + System.out.println(hex); + + String caps = new String("ThiS is A tEsT??"); + + Preprocessor.toLower(caps); + System.out.println(caps); + + System.out.println("All tests passed."); + } + */ + } diff --git a/Robust/src/Benchmarks/SingleTM/Intruder/RBTree.java b/Robust/src/Benchmarks/SingleTM/Intruder/RBTree.java index 94045033..52d33008 100644 --- a/Robust/src/Benchmarks/SingleTM/Intruder/RBTree.java +++ b/Robust/src/Benchmarks/SingleTM/Intruder/RBTree.java @@ -1,88 +1,704 @@ -#define ROTATE_LEFT(set, node) rotateLeft(set, node) -#define ROTATE_RIGHT(set, node) rotateRight(set, node) +/* ============================================================================= + * + * rbtree.java + * -- Red-black balanced binary search tree + * + * ============================================================================= + * + * Copyright (C) Sun Microsystems Inc., 2006. All Rights Reserved. + * Authors: Dave Dice, Nir Shavit, Ori Shalev. + * + * STM: Transactional Locking for Disjoint Access Parallelism + * + * Transactional Locking II, + * Dave Dice, Ori Shalev, Nir Shavit + * DISC 2006, Sept 2006, Stockholm, Sweden. + * + * ============================================================================= + * + * Modified by Chi Cao Minh + * + * ============================================================================= + * + * For the license of bayes/sort.h and bayes/sort.c, please see the header + * of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of kmeans, please see kmeans/LICENSE.kmeans + * + * ------------------------------------------------------------------------ + * + * For the license of ssca2, please see ssca2/COPYRIGHT + * + * ------------------------------------------------------------------------ + * + * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the + * header of the files. + * + * ------------------------------------------------------------------------ + * + * For the license of lib/rbtree.h and lib/rbtree.c, please see + * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree + * + * ------------------------------------------------------------------------ + * + * Unless otherwise noted, the following license applies to STAMP files: + * + * Copyright (c) 2007, Stanford University + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are + * met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * + * * Neither the name of Stanford University nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF + * THE POSSIBILITY OF SUCH DAMAGE. + * + * ============================================================================= + */ + +#define RED 0 +#define BLACK 1 + public class RBTree { - Node root; - // FIXME Test if this is correct - public int compare(int a, int b) { - return (a-b); - } - - public RBTree(void) { - root = null; - } - - public Node lookup(RBTree s, Object k) { - Node p = s.root; - while (p != null) { - int cmp = s.compare(k, p.k); - if (cmp == 0) { + Node root; + int compID; + + public RBTree() {} + + /* private Methods */ + /* lookup */ + private Node lookup(int k) + { + Node p = root; + + while(p != null) { + int cmp = compare(k,p.k); + if(cmp == 0) { + return p; + } + p = (cmp < 0) ? p.l : p.r; + } + + return null; + } + + + /* rotateLeft */ + private void rotateLeft(Node x) + { + Node r = x.r; + Node rl = r.l; + x.r = rl; + if(rl != null) { + rl.p = x; + } + + Node xp = x.p; + r.p = xp; + if (xp == null) { + root = r; + } else if (xp.l == x) { + xp.l = r; + } else { + xp.r = r; + } + r.l = x; + x.p = r; + } + + /* rotateRight */ + private void rotateRight(Node x) + { + Node l = x.l; + Node lr = l.r; + x.l = lr; + if (lr != null) { + lr.p = x; + } + Node xp = x.p; + l.p = xp; + if (xp == null) { + root = l; + } else if (xp.r == x) { + xp.r = l; + } else { + xp.l = l; + } + + l.r = x; + x.p = l; + } + + /* parentOf */ + private Node parentOf (Node n) + { + return ((n!=null) ? n.p : null); + } + + /* leftOf */ + private Node leftOf (Node n) + { + return ((n != null)? n.l : null); + } + + /* rightOf */ + private Node rightOf(Node n) + { + return ((n!= null) ? n.r : null); + } + + /* colorOf */ + private int colorOf(Node n) + { + return ((n!=null) ? n.c : BLACK); + } + + /* setColor */ + private void setColor(Node n, int c) + { + if ( n != null) { + n.c = c; + } + } + + /* fixAfterInsertion */ + private void fixAfterInsertion(Node x) + { + x.c = RED; + + while (x != null && x != root) { + Node xp = x.p; + if(xp.c != RED) { + break; + } + + if(parentOf(x) == leftOf(parentOf(parentOf(x)))) { + Node y = rightOf(parentOf(parentOf(x))); + if(colorOf(y) == RED) { + setColor(parentOf(x),BLACK); + setColor(y,BLACK); + setColor(parentOf(parentOf(x)),RED); + x = parentOf(parentOf(x)); + } else { + if ( x== rightOf(parentOf(x))) { + x = parentOf(x); + rotateLeft(x); + } + setColor(parentOf(x),BLACK); + setColor(parentOf(parentOf(x)),RED); + if(parentOf(parentOf(x)) != null) { + rotateRight(parentOf(parentOf(x))); + } + } + } else { + Node y = leftOf(parentOf(parentOf(x))); + if(colorOf(y) == RED) { + setColor(parentOf(x),BLACK); + setColor(y,BLACK); + setColor(parentOf(parentOf(x)),RED); + x = parentOf(parentOf(x)); + } else { + if (x == leftOf(parentOf(x))) { + x = parentOf(x); + rotateRight(x); + } + setColor(parentOf(x),BLACK); + setColor(parentOf(parentOf(x)),RED); + if (parentOf(parentOf(x)) != null) { + rotateLeft(parentOf(parentOf(x))); + } + } + } + } + + Node ro = root; + if(ro.c != BLACK) { + ro.c = BLACK; + } + } + + private Node insert(int k,Object v,Node n) + { + Node t = root; + if (t== null) { + if (n == null) { + return null; + } + /* Note: the following STs don't really need to be transactional */ + n.l = null; + n.r = null; + n.p = null; + n.k = k; + n.v = v; + n.c = BLACK; + root = n; + return null; + } + + while(true) { + int cmp = compare(k,t.k); + if (cmp == 0) { + return t; + } else if (cmp < 0) { + Node tl = t.l; + if (tl != null) { + t = tl; + } else { + n.l = null; + n.r = null; + n.k = k; + n.v = v; + n.p = t; + t.l = n; + fixAfterInsertion(n); + return null; + } + } else { /* cmp > 0 */ + Node tr = t.r; + if (tr != null) { + t = tr; + } else { + n.l = null; + n.r = null; + n.k = k; + n.v = v; + n.p = t; + t.r = n; + fixAfterInsertion(n); + return null; + } + } + } + } + + /* successor */ + private Node successor(Node t) + { + if ( t == null) { + return null; + } else if( t.r != null) { + Node p = t.r; + while (p.l != null) { + p = p.l; + } + return p; + } else { + Node p = t.p; + Node ch = t; + while (p != null && ch == p.r) { + ch = p; + p = p.p; + } + return p; + } + + } + + /* fixAfterDeletion */ + private void fixAfterDeletion(Node x) + { + while (x != root && colorOf(x) == BLACK) { + if ( x == leftOf(parentOf(x))) { + Node sib = rightOf(parentOf(x)); + if (colorOf(sib) == RED) { + setColor(sib,BLACK); + setColor(parentOf(x),RED); + rotateLeft(parentOf(x)); + sib = rightOf(parentOf(x)); + } + if(colorOf(leftOf(sib)) == BLACK && + colorOf(rightOf(sib)) == BLACK) { + setColor(sib,RED); + x = parentOf(x); + } else { + if(colorOf(rightOf(sib)) == BLACK) { + setColor(leftOf(sib),BLACK); + setColor(sib,RED); + rotateRight(sib); + sib = rightOf(parentOf(x)); + } + setColor(sib,colorOf(parentOf(x))); + setColor(parentOf(x),BLACK); + setColor(rightOf(sib),BLACK); + rotateLeft(parentOf(x)); + x = root; + } + } else { /* symmetric */ + Node sib = leftOf(parentOf(x)); + if(colorOf(sib) == RED) { + setColor(sib,BLACK); + setColor(parentOf(x),RED); + rotateRight(parentOf(x)); + sib = leftOf(parentOf(x)); + } + if (colorOf(rightOf(sib)) == BLACK && + colorOf(leftOf(sib)) == BLACK) { + setColor(sib,RED); + x = parentOf(x); + } else { + if(colorOf(leftOf(sib)) == BLACK) { + setColor(rightOf(sib), BLACK); + setColor(sib,RED); + rotateLeft(sib); + sib = leftOf(parentOf(x)); + } + setColor(sib,colorOf(parentOf(x))); + setColor(parentOf(x),BLACK); + setColor(leftOf(sib),BLACK); + rotateRight(parentOf(x)); + x = root; + } + } + } + + if (x != null && x.c != BLACK) { + x.c = BLACK; + } + } + + private Node deleteNode(Node p) { + /* + * If strictly internal, copy successor's element to p and then make p + * point to successor + */ + if(p.l != null && p.r != null) { + Node s = successor(p); + p.k = s.k; + p.v = s.v; + p = s; + } /* p has 2 children */ + + /* Start fixup at replacement node, if it exists */ + Node replacement = (p.l != null)? p.l : p.r; + + if (replacement != null) { + /* Link replacement to parent */ + replacement.p = p.p; + Node pp = p.p; + if(pp == null) { + root = replacement; + } else if( p == pp.l) { + pp.l = replacement; + } else { + pp.r = replacement; + } + + /* Null out links so they are OK to use by fixAfterDeletion */ + p.l = null; + p.r = null; + p.p = null; + + /* Fix replacement */ + if(p.c == BLACK) { + fixAfterDeletion(replacement); + } + } else if(p.p == null) { /* return if we are the only node */ + root = null; + } else { /* No children. Use self as phantom replacement and unlink */ + if (p.c == BLACK) { + fixAfterDeletion(p); + } + Node pp = p.p; + if(pp != null) { + if( p == pp.l) { + pp.l = null; + } else if( p == pp.r) { + pp.r = null; + } + p.p = null; + } + } + return p; + } + + + /* + * Diagnostic section + */ + + /* firstEntry */ + + private Node firstEntry() + { + Node p = root; + if( p != null) { + while ( p.l != null) { + p = p.l; + } + } return p; - } - if (cmp < 0) { - p = p.l; - } else { - p = p.r; - } - } - return null; - } - - /* - * Balancing operations. - * - * Implementations of rebalancings during insertion and deletion are - * slightly different than the CLR version. Rather than using dummy - * nilnodes, we use a set of accessors that deal properly with null. They - * are used to avoid messiness surrounding nullness checks in the main - * algorithms. - * - * From CLR - */ - public void rotateLeft(Node x) { - Node r = LDNODE(x, r); - Node rl = LDNODE(r, l); - STF(x, r, rl); - if (rl != null) { - STF(rl, p, x); - } - /* TODO: compute p = xp = x->p. Use xp for R-Values in following */ - Node xp = LDNODE(x, p); - STF(r, p, xp); - if (xp == NULL) { - STF(this, root, r); - } else if (LDNODE(xp, l) == x) { - STF(xp, l, r); - } else { - STF(xp, r, r); - } - } - - public rotateRight(Node x) { - Node l = LDNODE(x, l); - Node lr = LDNODE(l, r); - STF(x, l, lr); - if (lr != NULL) { - STF(lr, p, x); - } - Node xp = LDNODE(x, p); - STF(l, p, xp); - if (xp == NULL) { - STF(this, root, l); - } else if (LDNODE(xp, r) == x) { - STF(xp, r, l); - } else { - STF(xp, l, l); - } - STF(l, r, x); - STF(x, p, l); - } - - public Node parentOf(Node n) { - if (n ! = null) { - return LDNODE(n,p); - } - return null; - } + } + + /* verifyRedBlack */ + + private int verifyRedBlack(Node root,int depth) + { + int height_left; + int height_right; + + if ( root == null) { + return 1; + } + + height_left = verifyRedBlack(root.l,depth+1); + height_right = verifyRedBlack(root.r,depth+1); + if(height_left == 0 || height_right == 0) { + return 0; + } + if (height_left != height_right) { + System.out.println(" Imbalace @depth = " + depth + " : " + height_left + " " + height_right); + } + + if (root.l != null && root.l.p != root) { + System.out.println(" lineage"); + } + if (root.r != null && root.r.p != root) { + System.out.println(" lineage"); + } + + /* Red-Black alternation */ + if (root.c == RED) { + if (root.l != null && root.l.c != BLACK) { + System.out.println("VERIFY in verifyRedBlack"); + return 0; + } + + if (root.r != null && root.r.c != BLACK) { + System.out.println("VERIFY in verifyRedBlack"); + return 0; + } + return height_left; + } + if(root.c != BLACK) { + System.out.println("VERIFY in verifyRedBlack"); + return 0; + } + + return (height_left + 1); + } + + /* compareKeysDefault */ + private int compareKeysDefault (final int a,final int b) + { + return a - b; + } + + private int compare(int a,int b) + { + if(compID == 0) + return compareKeysDefault(a,b); + else + return compareKeysDefault(a,b); + } + + + + + + +/***************************************** + * public methods + *****************************************/ + + +/* ============================================================================= + * rbtree_verify + * ============================================================================= + long rbtree_verify (rbtree_t* s, long verbose); + */ + public int verify(int verbose) + { + if ( root == null) { + return 1; + } + if(verbose != 0) { + System.out.println("Integrity check: "); + } + + if (root.p != null) { + System.out.println(" (WARNING) root = " + root + " parent = " + root.p); + return -1; + } + if (root.c != BLACK) { + System.out.println(" (WARNING) root = " + root + " color = " + root.c); + } + + /* Weak check of binary-tree property */ + int ctr = 0; + Node its = firstEntry(); + while (its != null) { + ctr++; + Node child = its.l; + if ( child != null && child.p != its) { + System.out.println("bad parent"); + } + child = its.r; + if ( child != null && child.p != its) { + System.out.println("Bad parent"); + } + Node nxt = successor(its); + if (nxt == null) { + break; + } + if( compare(its.k,nxt.k) >= 0) { + System.out.println("Key order " + its + " ("+its.k+" "+its.v+") " + + nxt + " ("+nxt.k+" "+nxt.v+") "); + return -3; + } + its = nxt; + } + + int vfy = verifyRedBlack(root, 0); + if(verbose != 0) { + System.out.println(" Nodes = " + ctr + " Depth = " + vfy); + } + + return vfy; + + } + +/* ============================================================================= + * rbtree_alloc + * ============================================================================= + * rbtree_t* rbtree_alloc (long (*compare)(const void*, const void*)); + */ + public static RBTree alloc(int compID) + { + RBTree n = new RBTree(); + if (n != null) { + n.compID = compID; + n.root = null; + } + + return n; + } + + + +/* ============================================================================= + * rbtree_free + * ============================================================================= + * void rbtree_free (rbtree_t* r); + */ + + + +/* ============================================================================= + * rbtree_insert + * -- Returns TRUE on success + * ============================================================================= + * bool_t rbtree_insert (rbtree_t* r, void* key, void* val); + */ + public boolean insert(int key,Object val) + { + Node node = new Node(); + Node ex = insert(key,val,node); + if ( ex != null) { + node = null; + } + return ((ex == null) ? true : false); + } + + +/* ============================================================================= + * rbtree_delete + * ============================================================================= + * bool_t rbtree_delete (rbtree_t* r, void* key); + */ + public boolean deleteNode(int key) + { + Node node = null; + node = lookup(key); + + if(node != null) { + node = deleteNode(node); + } + if(node != null) { + } + return ((node != null) ? true : false); + + } + + + +/* ============================================================================= + * rbtree_update + * -- Return FALSE if had to insert node first + * ============================================================================= + * bool_t rbtree_update (rbtree_t* r, void* key, void* val); + */ + public boolean update(int key,Object val) + { + Node nn = new Node(); + Node ex = insert(key,val,nn); + if (ex != null) { + ex.v = val; + nn = null; + return true; + } + return false; + } + + + +/* ============================================================================= + * rbtree_get + * ============================================================================= + * void* rbtree_get (rbtree_t* r, void* key); + */ + public Object get(int key) + { + Node n = lookup(key); + if (n != null) { + Object val = n.v; + return val; + } + return null; + } + + + +/* ============================================================================= + * rbtree_contains + * ============================================================================= + * bool_t rbtree_contains (rbtree_t* r, void* key); + */ + public boolean contains(int key) + { + Node n = lookup(key); + + return (n != null); + } } + +/* ============================================================================= + * + * End of rbtree.java + * + * ============================================================================= + */ diff --git a/Robust/src/Benchmarks/SingleTM/Intruder/Stream.java b/Robust/src/Benchmarks/SingleTM/Intruder/Stream.java index 9d4bcc89..b7b2ac54 100644 --- a/Robust/src/Benchmarks/SingleTM/Intruder/Stream.java +++ b/Robust/src/Benchmarks/SingleTM/Intruder/Stream.java @@ -1,56 +1,71 @@ #define MAP_T RBTree -#define MAP_ALLOC(hash, cmp) RBTree() -#define MAP_INSERT(map, key, data) map.rbtree_insert(key, data) -#define MAP_CONTAINS(map, key) map.rbtree_contains(key); +#define MAP_ALLOC(hash, cmp) RBTree.alloc(cmp) +#define MAP_INSERT(map, key, data) map.insert(key, data) +#define MAP_CONTAINS(map, key) map.contains(key); +#define MAP_FIND(map,key) map.get(key); +#define MAP_REMOVE(map,key) map.deleteNode(key); public class Stream { int percentAttack; Random randomPtr; Vector_t allocVectorPtr; - Queue packetQueuePtr; + Queue_t packetQueuePtr; MAP_T attackMapPtr; - public Stream(int percentAttack) { - Stream streamPtr; + public Stream() {} + + + /* alloc */ + public static Stream alloc(int percentAttack) { + Stream streamPtr = new Stream(); if (percentAttack < 0 || percentAttack > 100) { System.out.print("Error: Invalid percentAttack value\n"); System.exit(0); } - this.percentAttack = percentAttack; - randomPtr = new Random(); - allocVectorPtr = vector_alloc(1); - if (allocVectorPtr == null) { + streamPtr.percentAttack = percentAttack; + + streamPtr.randomPtr = new Random(); + streamPtr.allocVectorPtr = Vector_t.vector_alloc(1); + if (streamPtr.allocVectorPtr == null) { System.out.print("Error: Vector allocation failed\n"); System.exit(0); } - packetQueuePtr = queue_alloc(1); - if (packetQueuePtr == null) { + streamPtr.packetQueuePtr = Queue_t.queue_alloc(1); + if (streamPtr.packetQueuePtr == null) { System.out.print("Error: Queue allocation failed\n"); System.exit(0); } - attackMapPtr = MAP_ALLOC(null, null); - if (attackMapPtr == null) { + streamPtr.attackMapPtr = MAP_ALLOC(0,0); + if (streamPtr.attackMapPtr == null) { System.out.print("Error: MAP_ALLOC failed\n"); System.exit(0); } + return streamPtr; } - public void splitIntoPackets(String str, int flowId, Random randomPtr, - Vector_t allocVectorPtr, Queue packetQueuePtr) + /* splintIntoPackets + * -- Packets will be equal-size chunks except for last one, which will have + * all extra bytes + */ + private void splitIntoPackets(String str, int flowId, Random randomPtr, + Vector_t allocVectorPtr, Queue_t packetQueuePtr) { int numByte = str.length(); int numPacket = randomPtr.random_generate() % numByte + 1; int numDataByte = numByte / numPacket; int p; + boolean status; + int beginIndex = 0; + int endIndex; + for (p = 0; p < (numPacket - 1); p++) { Packet bytes = new Packet(numDataByte); if (bytes == null) { System.out.printString("Error: Packet class allocation failed\n"); System.exit(-1); } - boolean status; status = allocVectorPtr.vector_pushBack(bytes); if (status == false) { System.out.printString("Error: Vector pushBack failed\n"); @@ -60,8 +75,7 @@ public class Stream { bytes.fragmentId = p; bytes.numFragment = numPacket; bytes.length = numDataByte; - int beginIndex = p * numDataByte; - int endIndex = beginIndex + numDataByte; + endIndex = beginIndex + numDataByte; String tmpstr = str.subString(beginIndex, endIndex); bytes.data = new String(tmpstr); status = packetQueuePtr.queue_push(bytes); @@ -69,10 +83,11 @@ public class Stream { System.out.printString("Error: Queue push failed\n"); System.exit(0); } + beginIndex = endIndex; } - boolean status; + int lastNumDataByte = numDataByte + numByte % numPacket; - Packet bytes = new Packet(lastNumDataByte); + Packet bytes = new Packet(0); if (bytes == null) { System.out.printString("Error: Packet class allocation failed\n"); System.exit(0); @@ -80,11 +95,11 @@ public class Stream { bytes.flowId = flowId; bytes.fragmentId = p; bytes.numFragment = numPacket; - bytes.length = lastNumDataByte; - int beginIndex = p * numDataByte; - int endIndex = beginIndex + lastNumDataByte; + bytes.length = str.length(); + + endIndex = numByte -1; String tmpstr = str.subString(beginIndex, endIndex); - bytes.data = new String(tmpstr); + bytes.data = new String(str); status = packetQueuePtr.queue_push(bytes); if (status == false) { System.out.printString("Error: Queue push failed\n"); @@ -92,20 +107,26 @@ public class Stream { } } - int stream_generate(Stream streamPtr, Dictionary dictionaryPtr, - int numFlow, int seed, int maxLength) + /*================================================== + /* stream_generate + * -- Returns number of attacks generated + /*==================================================*/ + + public int generate(Dictionary dictionaryPtr,int numFlow, int seed, int maxLength) { int numAttack = 0; + ERROR error = new ERROR(); + + Detector detectorPtr = Detector.alloc(); - int percentAttack = streamPtr.percentAttack; - Random randomPtr = streamPtr.randomPtr; - Vector_t allocVectorPtr = streamPtr.allocVectorPtr; - Queue packetQueuePtr = streamPtr.packetQueuePtr; - MAP_T attackMapPtr = streamPtr.attackMapPtr; + if(detectorPtr == null) + { + System.out.println("Assertion in Stream.generate"); + System.exit(1); + } + detectorPtr.addPreprocessor(2); // preprocessor_toLower - Detector detectorPtr = new Detector(); - //detectorPtr.detector_addPreprocessor( - randomPtr.random_seed(); + randomPtr.random_seed(seed); packetQueuePtr.queue_clear(); int range = '~' - ' ' + 1; @@ -115,12 +136,13 @@ public class Stream { } int f; + boolean status; for (f = 1; f <= numFlow; f++) { String str; if ((randomPtr.random_generate() % 100) < percentAttack) { - int s = randomPtr.random_generate() % global_numDefaultSignature; - str = dictionaryPtr.dictionary_get(s); - boolean status = MAP_INSERT(attackMapPtr, f, str); + int s = randomPtr.random_generate() % dictionaryPtr.global_numDefaultSignature; + str = dictionaryPtr.get(s); + status = MAP_INSERT(attackMapPtr, f, str); if (status == false) { System.out.printString("Assert failed: status is false\n"); System.exit(0); @@ -129,22 +151,26 @@ public class Stream { } else { /* Create random string */ int length = (randomPtr.random_generate() % maxLength) + 1; - str = new String[length+1]; - boolean status = allocVectorPtr.vector_pushBack(str); - if (status == null) { + status = allocVectorPtr.vector_pushBack(str); + + if (!status) { System.out.printString("Assert failed: status is null\n"); System.exit(0); } - char c[] = str.toCharArray(); + int l; + char c[] = new char[length+1]; for (l = 0; l < length; l++) { - c[l] = ' ' + (char) randomPtr.random_generate() % range; + c[l] =(char) (' ' + (char) (randomPtr.random_generate() % range)); } - c[l] = 0; + c[l] = '\0'; + str = new String(c); String str2 = new String(c); - int err = detectorPtr.detector_process(str2); - if (err == ERROR_SIGNATURE) { - boolean status = MAP_INSERT(attackMapPtr, f, str); - if (status == null) { + int err = detectorPtr.process(str2); + if (err == error.SIGNATURE) { + status = MAP_INSERT(attackMapPtr, f, str); + + System.out.println("Never here"); + if (!status) { System.out.printString("Assert failed status is null\n"); System.exit(0); } @@ -152,20 +178,30 @@ public class Stream { } } splitIntoPackets(str, f, randomPtr, allocVectorPtr, packetQueuePtr); + } packetQueuePtr.queue_shuffle(randomPtr); return numAttack; } - String stream_getPacket(Stream streamPtr) + /*======================================================== + * stream_getPacket + * -- If none, returns null + * ====================================================== + */ + Packet getPacket() { - return streamPtr.queue_pop(); + return (Packet)packetQueuePtr.queue_pop(); } - boolean stream_isAttack(Stream streamPtr, int flowId) + /* ======================================================= + * stream_isAttack + * ======================================================= + */ + boolean isAttack(int flowId) { - return MAP_CONTAINS(streamPtr.attackMapPtr, flowId); + return MAP_CONTAINS(attackMapPtr, flowId); } } -- 2.34.1