1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * https://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19 package org.apache.bcel.verifier.statics;
20
21 import java.util.ArrayList;
22 import java.util.List;
23 import java.util.Map;
24 import java.util.NavigableMap;
25 import java.util.TreeMap;
26
27 import org.apache.bcel.generic.Type;
28 import org.apache.bcel.verifier.exc.LocalVariableInfoInconsistentException;
29
30 /**
31 * A utility class holding the information about the name and the type of a local variable in a given slot (== index).
32 * This information often changes in course of byte code offsets.
33 */
34 public class LocalVariableInfo {
35
36 /**
37 * A contiguous, inclusive range of bytecode offsets sharing one variable name and one type.
38 */
39 private static final class Range {
40 private final int start;
41 private final int end; // inclusive
42 private final String name;
43 private final Type type;
44
45 Range(final int start, final int end, final String name, final Type type) {
46 this.start = start;
47 this.end = end;
48 this.name = name;
49 this.type = type;
50 }
51 }
52
53 /**
54 * The database of ranges, keyed by their start offset. Invariant: the stored ranges never overlap each other; additions overlapping an existing range
55 * with consistent information are coalesced into it, inconsistent ones are rejected. Storing ranges instead of one entry per offset keeps the work and
56 * memory proportional to the number of LocalVariableTable entries: the startPc and length fields are attacker-controlled in a malicious class file and
57 * would otherwise amplify each 10-byte table entry into up to 65,536 hashtable operations (CWE-407).
58 */
59 private final NavigableMap<Integer, Range> ranges = new TreeMap<>();
60
61 /**
62 * Constructs a new LocalVariableInfo.
63 */
64 public LocalVariableInfo() {
65 }
66
67 /**
68 * Adds some information about this local variable (slot).
69 *
70 * @param name variable name.
71 * @param startPc Range in which the variable is valid.
72 * @param length length of ...
73 * @param type variable type.
74 * @throws LocalVariableInfoInconsistentException Thrown if the new information conflicts with already gathered information.
75 */
76 public void add(final String name, final int startPc, final int length, final Type type) throws LocalVariableInfoInconsistentException {
77 final int endPc = startPc + length; // incl/incl-notation!
78 int mergedStart = startPc;
79 int mergedEnd = endPc;
80 // Only ranges starting at or before endPc can overlap [startPc, endPc]; since stored ranges never overlap each other, the first candidate is the
81 // last range starting at or before startPc.
82 Integer from = ranges.floorKey(startPc);
83 if (from == null) {
84 from = Integer.valueOf(startPc);
85 }
86 final List<Integer> merged = new ArrayList<>();
87 for (final Map.Entry<Integer, Range> entry : ranges.subMap(from, true, Integer.valueOf(endPc), true).entrySet()) {
88 final Range range = entry.getValue();
89 if (range.end < startPc) {
90 continue; // does not overlap.
91 }
92 final int offset = Math.max(startPc, range.start);
93 if (!range.name.equals(name)) {
94 throw new LocalVariableInfoInconsistentException(
95 "At bytecode offset '" + offset + "' a local variable has two different names: '" + range.name + "' and '" + name + "'.");
96 }
97 if (!range.type.equals(type)) {
98 throw new LocalVariableInfoInconsistentException(
99 "At bytecode offset '" + offset + "' a local variable has two different types: '" + range.type + "' and '" + type + "'.");
100 }
101 // Consistent overlap: coalesce, so the database stays proportional to the number of disjoint ranges.
102 mergedStart = Math.min(mergedStart, range.start);
103 mergedEnd = Math.max(mergedEnd, range.end);
104 merged.add(entry.getKey());
105 }
106 merged.forEach(ranges::remove);
107 ranges.put(Integer.valueOf(mergedStart), new Range(mergedStart, mergedEnd, name, type));
108 }
109
110 /**
111 * Returns the name of the local variable that uses this local variable slot at the given bytecode offset. Care for
112 * legal bytecode offsets yourself, otherwise the return value might be wrong. May return 'null' if nothing is known
113 * about the type of this local variable slot at the given bytecode offset.
114 *
115 * @param offset bytecode offset.
116 * @return The name of the local variable that uses this local variable slot at the given bytecode offset.
117 */
118 public String getName(final int offset) {
119 final Range range = lookup(offset);
120 return range != null ? range.name : null;
121 }
122
123 /**
124 * Returns the type of the local variable that uses this local variable slot at the given bytecode offset. Care for
125 * legal bytecode offsets yourself, otherwise the return value might be wrong. May return 'null' if nothing is known
126 * about the type of this local variable slot at the given bytecode offset.
127 *
128 * @param offset bytecode offset.
129 * @return The type of the local variable that uses this local variable slot at the given bytecode offset.
130 */
131 public Type getType(final int offset) {
132 final Range range = lookup(offset);
133 return range != null ? range.type : null;
134 }
135
136 /**
137 * Returns the range covering the given bytecode offset, or {@code null} if no range covers it. Since the stored ranges never overlap, only the range
138 * with the greatest start offset at or below the given offset can cover it.
139 */
140 private Range lookup(final int offset) {
141 final Map.Entry<Integer, Range> entry = ranges.floorEntry(Integer.valueOf(offset));
142 return entry != null && entry.getValue().end >= offset ? entry.getValue() : null;
143 }
144 }