discussion6 2 Breaking the System

CS61B

Below is the SNode class, along with a flawed implementation of the Stack ADT, BadIntStack.

public class BadIntStack {
    public class SNode {
            public Integer val;
            public SNode prev;
            public SNode(Integer v, SNode p) {
                val = v;
                prev = p;
            }
            public SNode(Integer v) {
                this(v, null);
            }
    }
            public SNode top;
            public boolean isEmpty() {
                return top == null;
            }
            public void push(Integer num) {
                top = new SNode(num, top);
            }
            public Integer pop() {
                Integer ans = top.val;
                top = top.prev;
                return ans;
            }
            public Integer peek() {
                return top.val;
            }
        public static void main(String[] args) {
            BadIntStack trap = new BadIntStack();
            // Your exploit here
            while (!trap.isEmpty()) {
                trap.pop();
            }
            System.out.println("This print statement is unreachable!");
        }
}

Fill in the Exploiter1 class so that it prints "Success!" by causing BadIntStack to produce a NullPointerException.

class Exploiter1 {
    public static void main(String[] args) {
        try {
    // Your exploit here!
            BadIntStack newStack = new BadIntStack();
            newStack.pop();
        } catch (NullPointerException e) {
            System.out.println("Success!");
        }
    }
}

Now, fill in the client class Exploiter2 so that it creates an "infinitely long" stack.

class Exploiter2 {
    public static void main(String[] args) {
        BadIntStack trap = new BadIntStack();
        // Your exploit here!
        trap.push(new Integer(1));
        trap.top.prev = trap.top;
        while(!trap.isEmpty()) {
            trap.pop();
        }
        System.out.println("This print statement is unreachable!");
    }
}

How can we change the BadIntStack class so that it won’t throw NullPointerExceptions
or allow ne’er-do-wells to produce endless stacks?

注意补上的一句

trap.top.prev = trap.top;

它的意思是：

像这样：

再回到原来的pop()方法的代码：

public Integer pop() {
    Integer ans = top.val;
    top = top.prev;
    return ans;
}

top = top.prev;

这句话不会对top造成任何影响，刚才的环形结构没被破坏，所以一直在运行while语句里的代码，没有办法执行print语句。

这道题让我想起最开始几堂课的disc3里的SNode,SList那一部分，有很多这类结构，可能并没有完全掌握，到了这儿又不会了。