diff options
Diffstat (limited to 'plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/deobfuscator/IrreducibleCFGDeobfuscator.java')
-rw-r--r-- | plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/deobfuscator/IrreducibleCFGDeobfuscator.java | 245 |
1 files changed, 245 insertions, 0 deletions
diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/deobfuscator/IrreducibleCFGDeobfuscator.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/deobfuscator/IrreducibleCFGDeobfuscator.java new file mode 100644 index 000000000000..31e171e214d5 --- /dev/null +++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/deobfuscator/IrreducibleCFGDeobfuscator.java @@ -0,0 +1,245 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.jetbrains.java.decompiler.modules.decompiler.deobfuscator; + +import org.jetbrains.java.decompiler.modules.decompiler.StatEdge; +import org.jetbrains.java.decompiler.modules.decompiler.stats.BasicBlockStatement; +import org.jetbrains.java.decompiler.modules.decompiler.stats.Statement; + +import java.util.HashMap; +import java.util.HashSet; +import java.util.Set; + + +public class IrreducibleCFGDeobfuscator { + + + public static boolean isStatementIrreducible(Statement statement) { + + class Node { + public Integer id; + public Set<Node> preds = new HashSet<Node>(); + public Set<Node> succs = new HashSet<Node>(); + + public Node(Integer id) { + this.id = id; + } + } + + HashMap<Integer, Node> mapNodes = new HashMap<Integer, Node>(); + + // checking exceptions and creating nodes + for (Statement stat : statement.getStats()) { + if (!stat.getSuccessorEdges(StatEdge.TYPE_EXCEPTION).isEmpty()) { + return false; + } + + mapNodes.put(stat.id, new Node(stat.id)); + } + + // connecting nodes + for (Statement stat : statement.getStats()) { + Node node = mapNodes.get(stat.id); + + for (Statement succ : stat.getNeighbours(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD)) { + Node nodeSucc = mapNodes.get(succ.id); + + node.succs.add(nodeSucc); + nodeSucc.preds.add(node); + } + } + + // transforming and reducing the graph + while (true) { + int ttype = 0; + Node node = null; + + for (Node nd : mapNodes.values()) { + if (nd.succs.contains(nd)) { // T1 + ttype = 1; + } + else if (nd.preds.size() == 1) { // T2 + ttype = 2; + } + + if (ttype != 0) { + node = nd; + break; + } + } + + if (node != null) { + if (ttype == 1) { + node.succs.remove(node); + node.preds.remove(node); + } + else { + Node pred = node.preds.iterator().next(); + + pred.succs.addAll(node.succs); + pred.succs.remove(node); + + for (Node succ : node.succs) { + succ.preds.remove(node); + succ.preds.add(pred); + } + + mapNodes.remove(node.id); + } + } + else { // no transformation applicable + return mapNodes.size() > 1; // reducible iff one node remains + } + } + } + + + private static Statement getCandidateForSplitting(Statement statement) { + + Statement candidateForSplitting = null; + int sizeCandidateForSplitting = Integer.MAX_VALUE; + int succsCandidateForSplitting = Integer.MAX_VALUE; + + for (Statement stat : statement.getStats()) { + + Set<Statement> setPreds = stat.getNeighboursSet(StatEdge.TYPE_REGULAR, Statement.DIRECTION_BACKWARD); + + if (setPreds.size() > 1) { + int succCount = stat.getNeighboursSet(StatEdge.TYPE_REGULAR, Statement.DIRECTION_FORWARD).size(); + if (succCount <= succsCandidateForSplitting) { + int size = getStatementSize(stat) * (setPreds.size() - 1); + + if (succCount < succsCandidateForSplitting || + size < sizeCandidateForSplitting) { + candidateForSplitting = stat; + sizeCandidateForSplitting = size; + succsCandidateForSplitting = succCount; + } + } + } + } + + return candidateForSplitting; + } + + public static boolean splitIrreducibleNode(Statement statement) { + + Statement splitnode = getCandidateForSplitting(statement); + if (splitnode == null) { + return false; + } + + StatEdge enteredge = splitnode.getPredecessorEdges(StatEdge.TYPE_REGULAR).iterator().next(); + + // copy the smallest statement + Statement splitcopy = copyStatement(splitnode, null, new HashMap<Statement, Statement>()); + initCopiedStatement(splitcopy); + + // insert the copy + splitcopy.setParent(statement); + statement.getStats().addWithKey(splitcopy, splitcopy.id); + + // switch input edges + for (StatEdge prededge : splitnode.getPredecessorEdges(Statement.STATEDGE_DIRECT_ALL)) { + if (prededge.getSource() == enteredge.getSource() || + prededge.closure == enteredge.getSource()) { + splitnode.removePredecessor(prededge); + prededge.getSource().changeEdgeNode(Statement.DIRECTION_FORWARD, prededge, splitcopy); + splitcopy.addPredecessor(prededge); + } + } + + // connect successors + for (StatEdge succ : splitnode.getSuccessorEdges(Statement.STATEDGE_DIRECT_ALL)) { + splitcopy.addSuccessor(new StatEdge(succ.getType(), splitcopy, succ.getDestination(), succ.closure)); + } + + return true; + } + + private static int getStatementSize(Statement statement) { + + int res = 0; + + if (statement.type == Statement.TYPE_BASICBLOCK) { + res = ((BasicBlockStatement)statement).getBlock().getSeq().length(); + } + else { + for (Statement stat : statement.getStats()) { + res += getStatementSize(stat); + } + } + + return res; + } + + private static Statement copyStatement(Statement from, Statement to, HashMap<Statement, Statement> mapAltToCopies) { + + if (to == null) { + // first outer invocation + to = from.getSimpleCopy(); + mapAltToCopies.put(from, to); + } + + // copy statements + for (Statement st : from.getStats()) { + Statement stcopy = st.getSimpleCopy(); + + to.getStats().addWithKey(stcopy, stcopy.id); + mapAltToCopies.put(st, stcopy); + } + + // copy edges + for (int i = 0; i < from.getStats().size(); i++) { + Statement stold = from.getStats().get(i); + Statement stnew = to.getStats().get(i); + + for (StatEdge edgeold : stold.getSuccessorEdges(Statement.STATEDGE_DIRECT_ALL)) { + // type cannot be TYPE_EXCEPTION (checked in isIrreducibleTriangle) + StatEdge edgenew = new StatEdge(edgeold.getType(), stnew, + mapAltToCopies.containsKey(edgeold.getDestination()) + ? mapAltToCopies.get(edgeold.getDestination()) + : edgeold.getDestination(), + mapAltToCopies.containsKey(edgeold.closure) + ? mapAltToCopies.get(edgeold.closure) + : edgeold.closure); + + stnew.addSuccessor(edgenew); + } + } + + // recurse statements + for (int i = 0; i < from.getStats().size(); i++) { + Statement stold = from.getStats().get(i); + Statement stnew = to.getStats().get(i); + + copyStatement(stold, stnew, mapAltToCopies); + } + + return to; + } + + private static void initCopiedStatement(Statement statement) { + + statement.initSimpleCopy(); + statement.setCopied(true); + + for (Statement st : statement.getStats()) { + st.setParent(statement); + initCopiedStatement(st); + } + } +} |