@Test public void testDifferentActionPreservation() { BDD slash32 = PKT.getDstIp().value(Ip.parse("1.2.3.4").asLong()); BDD tcp = PKT.getIpProtocol().value(IpProtocol.TCP); BDD not80 = tcp.and(PKT.getDstPort().value(80).not()); List<BDD> bdds = ImmutableList.of(slash32.and(not80), PKT.getFactory().one(), slash32); List<LineAction> actions = ImmutableList.of(DENY, PERMIT, PERMIT); List<PermitAndDenyBdds> permitAndDenyBdds = toPermitAndDenyBdds(bdds, actions); BlockingProperties blockingProperties = findBlockingPropsForLine(2, permitAndDenyBdds); assertThat(blockingProperties.getBlockingLineNums(), contains(0, 1)); assertTrue(blockingProperties.getDiffAction()); List<LineAction> sameActions = ImmutableList.of(PERMIT, PERMIT, PERMIT); permitAndDenyBdds = toPermitAndDenyBdds(bdds, sameActions); blockingProperties = findBlockingPropsForLine(2, permitAndDenyBdds); assertThat(blockingProperties.getBlockingLineNums(), contains(1)); assertFalse(blockingProperties.getDiffAction()); List<LineAction> actionsAndCover = ImmutableList.of(DENY, DENY, PERMIT); permitAndDenyBdds = toPermitAndDenyBdds(bdds, actionsAndCover); blockingProperties = findBlockingPropsForLine(2, permitAndDenyBdds); assertThat(blockingProperties.getBlockingLineNums(), contains(1)); assertTrue(blockingProperties.getDiffAction()); }
@VisibleForTesting static BlockingProperties findBlockingPropsForLine( int blockedLineNum, List<PermitAndDenyBdds> bdds) { PermitAndDenyBdds blockedLine = bdds.get(blockedLineNum); ImmutableSortedSet.Builder<LineAndWeight> linesByWeight = ImmutableSortedSet.orderedBy(LineAndWeight.COMPARATOR); PermitAndDenyBdds restOfLine = blockedLine; boolean diffAction = false; for (int prevLineNum = 0; prevLineNum < blockedLineNum && !restOfLine.isZero(); prevLineNum++) { PermitAndDenyBdds prevLine = bdds.get(prevLineNum); if (!prevLine.getMatchBdd().andSat(restOfLine.getMatchBdd())) { continue; } BDD blockedLineOverlap = prevLine.getMatchBdd().and(blockedLine.getMatchBdd()); linesByWeight.add(new LineAndWeight(prevLineNum, blockedLineOverlap.satCount())); diffAction = diffAction || takeDifferentActions(prevLine, restOfLine); restOfLine = restOfLine.diff(prevLine.getMatchBdd()); } ImmutableSortedSet.Builder<Integer> answerLines = ImmutableSortedSet.naturalOrder(); restOfLine = blockedLine; boolean needDiffAction = diffAction; for (LineAndWeight line : linesByWeight.build()) { int curLineNum = line.getLine(); PermitAndDenyBdds curLine = bdds.get(curLineNum); boolean curDiff = takeDifferentActions(curLine, blockedLine); if (!restOfLine.isZero() || needDiffAction && curDiff) { restOfLine = restOfLine.diff(curLine.getMatchBdd()); answerLines.add(curLineNum); needDiffAction = needDiffAction && !curDiff; } if (restOfLine.isZero() && !needDiffAction) { break; } } return new BlockingProperties(answerLines.build(), diffAction); }
FilterLineReachabilityAnswerer extends Answerer { @VisibleForTesting static BlockingProperties findBlockingPropsForLine( int blockedLineNum, List<PermitAndDenyBdds> bdds) { PermitAndDenyBdds blockedLine = bdds.get(blockedLineNum); ImmutableSortedSet.Builder<LineAndWeight> linesByWeight = ImmutableSortedSet.orderedBy(LineAndWeight.COMPARATOR); PermitAndDenyBdds restOfLine = blockedLine; boolean diffAction = false; for (int prevLineNum = 0; prevLineNum < blockedLineNum && !restOfLine.isZero(); prevLineNum++) { PermitAndDenyBdds prevLine = bdds.get(prevLineNum); if (!prevLine.getMatchBdd().andSat(restOfLine.getMatchBdd())) { continue; } BDD blockedLineOverlap = prevLine.getMatchBdd().and(blockedLine.getMatchBdd()); linesByWeight.add(new LineAndWeight(prevLineNum, blockedLineOverlap.satCount())); diffAction = diffAction || takeDifferentActions(prevLine, restOfLine); restOfLine = restOfLine.diff(prevLine.getMatchBdd()); } ImmutableSortedSet.Builder<Integer> answerLines = ImmutableSortedSet.naturalOrder(); restOfLine = blockedLine; boolean needDiffAction = diffAction; for (LineAndWeight line : linesByWeight.build()) { int curLineNum = line.getLine(); PermitAndDenyBdds curLine = bdds.get(curLineNum); boolean curDiff = takeDifferentActions(curLine, blockedLine); if (!restOfLine.isZero() || needDiffAction && curDiff) { restOfLine = restOfLine.diff(curLine.getMatchBdd()); answerLines.add(curLineNum); needDiffAction = needDiffAction && !curDiff; } if (restOfLine.isZero() && !needDiffAction) { break; } } return new BlockingProperties(answerLines.build(), diffAction); } }
FilterLineReachabilityAnswerer extends Answerer { @VisibleForTesting static BlockingProperties findBlockingPropsForLine( int blockedLineNum, List<PermitAndDenyBdds> bdds) { PermitAndDenyBdds blockedLine = bdds.get(blockedLineNum); ImmutableSortedSet.Builder<LineAndWeight> linesByWeight = ImmutableSortedSet.orderedBy(LineAndWeight.COMPARATOR); PermitAndDenyBdds restOfLine = blockedLine; boolean diffAction = false; for (int prevLineNum = 0; prevLineNum < blockedLineNum && !restOfLine.isZero(); prevLineNum++) { PermitAndDenyBdds prevLine = bdds.get(prevLineNum); if (!prevLine.getMatchBdd().andSat(restOfLine.getMatchBdd())) { continue; } BDD blockedLineOverlap = prevLine.getMatchBdd().and(blockedLine.getMatchBdd()); linesByWeight.add(new LineAndWeight(prevLineNum, blockedLineOverlap.satCount())); diffAction = diffAction || takeDifferentActions(prevLine, restOfLine); restOfLine = restOfLine.diff(prevLine.getMatchBdd()); } ImmutableSortedSet.Builder<Integer> answerLines = ImmutableSortedSet.naturalOrder(); restOfLine = blockedLine; boolean needDiffAction = diffAction; for (LineAndWeight line : linesByWeight.build()) { int curLineNum = line.getLine(); PermitAndDenyBdds curLine = bdds.get(curLineNum); boolean curDiff = takeDifferentActions(curLine, blockedLine); if (!restOfLine.isZero() || needDiffAction && curDiff) { restOfLine = restOfLine.diff(curLine.getMatchBdd()); answerLines.add(curLineNum); needDiffAction = needDiffAction && !curDiff; } if (restOfLine.isZero() && !needDiffAction) { break; } } return new BlockingProperties(answerLines.build(), diffAction); } FilterLineReachabilityAnswerer(Question question, IBatfish batfish); }
FilterLineReachabilityAnswerer extends Answerer { @VisibleForTesting static BlockingProperties findBlockingPropsForLine( int blockedLineNum, List<PermitAndDenyBdds> bdds) { PermitAndDenyBdds blockedLine = bdds.get(blockedLineNum); ImmutableSortedSet.Builder<LineAndWeight> linesByWeight = ImmutableSortedSet.orderedBy(LineAndWeight.COMPARATOR); PermitAndDenyBdds restOfLine = blockedLine; boolean diffAction = false; for (int prevLineNum = 0; prevLineNum < blockedLineNum && !restOfLine.isZero(); prevLineNum++) { PermitAndDenyBdds prevLine = bdds.get(prevLineNum); if (!prevLine.getMatchBdd().andSat(restOfLine.getMatchBdd())) { continue; } BDD blockedLineOverlap = prevLine.getMatchBdd().and(blockedLine.getMatchBdd()); linesByWeight.add(new LineAndWeight(prevLineNum, blockedLineOverlap.satCount())); diffAction = diffAction || takeDifferentActions(prevLine, restOfLine); restOfLine = restOfLine.diff(prevLine.getMatchBdd()); } ImmutableSortedSet.Builder<Integer> answerLines = ImmutableSortedSet.naturalOrder(); restOfLine = blockedLine; boolean needDiffAction = diffAction; for (LineAndWeight line : linesByWeight.build()) { int curLineNum = line.getLine(); PermitAndDenyBdds curLine = bdds.get(curLineNum); boolean curDiff = takeDifferentActions(curLine, blockedLine); if (!restOfLine.isZero() || needDiffAction && curDiff) { restOfLine = restOfLine.diff(curLine.getMatchBdd()); answerLines.add(curLineNum); needDiffAction = needDiffAction && !curDiff; } if (restOfLine.isZero() && !needDiffAction) { break; } } return new BlockingProperties(answerLines.build(), diffAction); } FilterLineReachabilityAnswerer(Question question, IBatfish batfish); @Override TableAnswerElement answer(NetworkSnapshot snapshot); }
FilterLineReachabilityAnswerer extends Answerer { @VisibleForTesting static BlockingProperties findBlockingPropsForLine( int blockedLineNum, List<PermitAndDenyBdds> bdds) { PermitAndDenyBdds blockedLine = bdds.get(blockedLineNum); ImmutableSortedSet.Builder<LineAndWeight> linesByWeight = ImmutableSortedSet.orderedBy(LineAndWeight.COMPARATOR); PermitAndDenyBdds restOfLine = blockedLine; boolean diffAction = false; for (int prevLineNum = 0; prevLineNum < blockedLineNum && !restOfLine.isZero(); prevLineNum++) { PermitAndDenyBdds prevLine = bdds.get(prevLineNum); if (!prevLine.getMatchBdd().andSat(restOfLine.getMatchBdd())) { continue; } BDD blockedLineOverlap = prevLine.getMatchBdd().and(blockedLine.getMatchBdd()); linesByWeight.add(new LineAndWeight(prevLineNum, blockedLineOverlap.satCount())); diffAction = diffAction || takeDifferentActions(prevLine, restOfLine); restOfLine = restOfLine.diff(prevLine.getMatchBdd()); } ImmutableSortedSet.Builder<Integer> answerLines = ImmutableSortedSet.naturalOrder(); restOfLine = blockedLine; boolean needDiffAction = diffAction; for (LineAndWeight line : linesByWeight.build()) { int curLineNum = line.getLine(); PermitAndDenyBdds curLine = bdds.get(curLineNum); boolean curDiff = takeDifferentActions(curLine, blockedLine); if (!restOfLine.isZero() || needDiffAction && curDiff) { restOfLine = restOfLine.diff(curLine.getMatchBdd()); answerLines.add(curLineNum); needDiffAction = needDiffAction && !curDiff; } if (restOfLine.isZero() && !needDiffAction) { break; } } return new BlockingProperties(answerLines.build(), diffAction); } FilterLineReachabilityAnswerer(Question question, IBatfish batfish); @Override TableAnswerElement answer(NetworkSnapshot snapshot);  }