#1152 OpcodeStack doesn't handle isreachonlybranch correctly

2.0.3
closed-fixed
Core (142)
8
2013-10-29
2012-12-30
No

Given the following snippet

public class ReachedOnlyByBranchProblem {

public void problem(Collection<String> strings, int i) {

for (String s : strings) {
someMethod(s, i);
}

someMethod("hello world", 0);
}

public void someMethod(String s, int i) {
}
}

which translate to

public void problem(java.util.Collection<java.lang.String>, int);
flags: ACC_PUBLIC
Signature: #17 //
(Ljava/util/Collection<Ljava/lang/String;>;I)V
Code:
stack=3, locals=5, args_size=3
0: aload_1
1: invokeinterface #18, 1 // InterfaceMethod
java/util/Collection.iterator:()Ljava/util/Iterator;
6: astore 4
8: goto 28
11: aload 4
13: invokeinterface #24, 1 // InterfaceMethod
java/util/Iterator.next:()Ljava/lang/Object;
18: checkcast #30 // class java/lang/String
21: astore_3
22: aload_0
23: aload_3
24: iload_2
25: invokevirtual #32 // Method
someMethod:(Ljava/lang/String;I)V
28: aload 4
30: invokeinterface #36, 1 // InterfaceMethod
java/util/Iterator.hasNext:()Z
35: ifne 11
38: aload_0
39: ldc #40 // String hello world
41: iconst_0
42: invokevirtual #32 // Method
someMethod:(Ljava/lang/String;I)V
45: return

At line 11, when OpcodeStack.sawOpcode executes, it calls

precomputation(dbc);
which calls
mergeJumps(dbc);

mergeJump sees that

} else if (isReachOnlyByBranch() && !stackUpdated) {

and clears the stack, which makes sense. It then does

setTop(true);

This unfortunately causes opcode processing to stop in sawOpcode

if (isTop()) {
encountedTop = true;
return;
}

and so the ALOAD 4 at byte offset 11, never causes a push onto the
stack for Register 4

It gets worse than this, however, as

isReachOnlyByBranch() appears to be stuck on, and so further opcodes
also are seen as the beginning of a branch-in-only opcode and this same
pattern occurs, that being: the stack is cleared, and the processing of
opcodes are bypassed. This happens for the rest of the method.

Discussion

  • William Pugh

    William Pugh - 2013-01-24

    The problem is that you are using a @CustomUserValue detector.

    To handle backedges in the opcode stack analysis, we do iterative analysis. We used to do this for each detector, but to make things more efficient we now do this once and story the backedge information in a JumpInfo. The problem is that if you use custom user values, you can't use this.

    I'll create a TestingGroup detector that uses iterative computation to compute JumpInfo so show you what you need to do.

     
  • William Pugh

    William Pugh - 2013-01-24
    • status: open --> open-accepted
     
  • William Pugh

    William Pugh - 2013-01-24

    Dave,
    Do you have an example of a detector using a CustomUserValue?

     
  • William Pugh

    William Pugh - 2013-01-24

    Actually, from looking at fb-contrib, it looks like you are just directly extending BytecodeScanningDetector.

    By the way, isReachOnlyByBranch gets reset by OpcodeStack.mergeJumps(DismantleBytecode)

     
  • Dave Brosius

    Dave Brosius - 2013-08-10

    Given this method

    public synchronized int[] getAllLevelSize()
    {
        int[] counts = new int[generations.length];
        for (int i = 0; i < counts.length; i++)
            counts[i] = generations[i].size();
        return counts;
    }
    

    found here: https://git-wip-us.apache.org/repos/asf?p=cassandra.git;a=blob;f=src/java/org/apache/cassandra/db/compaction/LeveledManifest.java;h=7a0a9271c7facc555b1c5ae04aef8517b202fddb;hb=c27a161920a2227cd04f8338a75732920694b1db#l311

    the OpcodeStack detector incorrectly tracks the contents of the stack after the downward branching goto at the beginning of the for loop

    Here's the byte code: look at opcode at offset 13, at the end of that instruction the stack should contain 1 element

    public synchronized int[] getAllLevelSize();
    flags: ACC_PUBLIC, ACC_SYNCHRONIZED
    Code:
      stack=4, locals=3, args_size=1
         0: aload_0      
         1: getfield      #78                 // Field generations:[Ljava/util/List;
         4: arraylength  
         5: newarray       int
         7: astore_1     
         8: iconst_0     
         9: istore_2     
        10: goto          30
        13: aload_1      
        14: iload_2      
        15: aload_0      
        16: getfield      #78                 // Field generations:[Ljava/util/List;
        19: iload_2      
        20: aaload       
        21: invokeinterface #435,  1          // InterfaceMethod java/util/List.size:()I
        26: iastore      
        27: iinc          2, 1
        30: iload_2      
        31: aload_1      
        32: arraylength  
        33: if_icmplt     13
        36: aload_1      
        37: areturn
    

    Here is the the output of the stack size after every instruction, notice after 13, the size is 0, which is wrong.

    After Opcode: 0 Stack Size is: 1
    After Opcode: 1 Stack Size is: 1
    After Opcode: 4 Stack Size is: 1
    After Opcode: 5 Stack Size is: 1
    After Opcode: 7 Stack Size is: 0
    After Opcode: 8 Stack Size is: 1
    After Opcode: 9 Stack Size is: 0
    After Opcode: 10 Stack Size is: 0
    After Opcode: 13 Stack Size is: 0
    After Opcode: 14 Stack Size is: 0
    After Opcode: 15 Stack Size is: 0
    After Opcode: 16 Stack Size is: 0
    After Opcode: 19 Stack Size is: 0
    After Opcode: 20 Stack Size is: 0
    After Opcode: 21 Stack Size is: 0
    After Opcode: 26 Stack Size is: 0
    After Opcode: 27 Stack Size is: 0
    After Opcode: 30 Stack Size is: 1
    After Opcode: 31 Stack Size is: 2
    After Opcode: 32 Stack Size is: 2
    After Opcode: 33 Stack Size is: 0
    After Opcode: 36 Stack Size is: 1
    After Opcode: 37 Stack Size is: 0
    

    This dump was created using a detector like this

    package com.mebigfatguy.fbcontrib.detect;
    
    import java.io.FileWriter;
    import java.io.IOException;
    import java.io.PrintWriter;
    
    import org.apache.bcel.classfile.Code;
    
    import edu.umd.cs.findbugs.BugReporter;
    import edu.umd.cs.findbugs.BytecodeScanningDetector;
    import edu.umd.cs.findbugs.OpcodeStack;
    
    public class OCSDebugger extends BytecodeScanningDetector {
    
        OpcodeStack stack = new OpcodeStack();
        PrintWriter pw = null;
    
        public OCSDebugger(BugReporter bugReporter) {
        }
    
        public void visitCode(Code obj) {
            stack.resetForMethodEntry(this);
            if (getClassContext().getJavaClass().getClassName().contains("LeveledManifest") && getMethod().getName().equals("getAllLevelSize")) {
                try {
                    pw = new PrintWriter(new FileWriter("/home/dave/Desktop/OCS.txt"));
                    super.visitCode(obj);
                } catch (IOException e) {
                } finally {
                    pw.close();
                    pw = null;
                }             
            }
        }
    
        public void sawOpcode(int seen) {
            stack.sawOpcode(this, seen);
            pw.println("After Opcode: " + getPC() + " Stack Size is: " + stack.getStackDepth());
        }
    }
    

    The problem is in OpcodeStack.precomputation's call of mergeJumps

    boolean wasReachOnlyByBranch = isReachOnlyByBranch();   is set to true
    

    and so this code is executed

    else if (isReachOnlyByBranch() && !stackUpdated) {
            stack.clear();
    

    and

    setTop(true);
    

    so once top has been set, when it exits and goes back to OpcodeStack.sawOpcode,

    you get a quick exit from

    if (isTop()) {
                encountedTop = true;
                return;
            }
    

    This of course breaks all kinds of detectors because the stack is wrong at this point, and ongoing until a complete pop of args occurs in the source.

     
    Last edit: Dave Brosius 2013-08-10
  • William Pugh

    William Pugh - 2013-10-29
    • status: open-accepted --> closed-fixed
    • Group: --> 2.0.3
     
  • William Pugh

    William Pugh - 2013-10-29

    Partially resolved through use of StackMap analysis

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.





No, thanks