-
Notifications
You must be signed in to change notification settings - Fork 5.7k
/
AutoVersionTrackingTask.java
1381 lines (1107 loc) · 48.8 KB
/
AutoVersionTrackingTask.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/* ###
* IP: GHIDRA
*
* 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:https://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 ghidra.feature.vt.gui.actions;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import javax.swing.SwingConstants;
import ghidra.feature.vt.api.correlator.program.CombinedFunctionAndDataReferenceProgramCorrelatorFactory;
import ghidra.feature.vt.api.correlator.program.DataReferenceProgramCorrelatorFactory;
import ghidra.feature.vt.api.correlator.program.DuplicateFunctionMatchProgramCorrelatorFactory;
import ghidra.feature.vt.api.correlator.program.ExactDataMatchProgramCorrelatorFactory;
import ghidra.feature.vt.api.correlator.program.ExactMatchBytesProgramCorrelatorFactory;
import ghidra.feature.vt.api.correlator.program.ExactMatchInstructionsProgramCorrelatorFactory;
import ghidra.feature.vt.api.correlator.program.ExactMatchMnemonicsProgramCorrelatorFactory;
import ghidra.feature.vt.api.correlator.program.FunctionReferenceProgramCorrelatorFactory;
import ghidra.feature.vt.api.correlator.program.SymbolNameProgramCorrelatorFactory;
import ghidra.feature.vt.api.correlator.program.VTAbstractReferenceProgramCorrelatorFactory;
import ghidra.feature.vt.api.main.VTAssociation;
import ghidra.feature.vt.api.main.VTAssociationManager;
import ghidra.feature.vt.api.main.VTAssociationStatus;
import ghidra.feature.vt.api.main.VTAssociationType;
import ghidra.feature.vt.api.main.VTMarkupItem;
import ghidra.feature.vt.api.main.VTMatch;
import ghidra.feature.vt.api.main.VTMatchSet;
import ghidra.feature.vt.api.main.VTProgramCorrelator;
import ghidra.feature.vt.api.main.VTProgramCorrelatorFactory;
import ghidra.feature.vt.api.main.VTSession;
import ghidra.feature.vt.api.util.VTAssociationStatusException;
import ghidra.feature.vt.api.util.VTOptions;
import ghidra.feature.vt.gui.plugin.AddressCorrelatorManager;
import ghidra.feature.vt.gui.task.ApplyMarkupItemTask;
import ghidra.feature.vt.gui.util.ImpliedMatchUtils;
import ghidra.feature.vt.gui.util.MatchInfo;
import ghidra.feature.vt.gui.util.MatchInfoFactory;
import ghidra.feature.vt.gui.util.VTOptionDefines;
import ghidra.framework.options.ToolOptions;
import ghidra.program.model.address.Address;
import ghidra.program.model.address.AddressSetView;
import ghidra.program.model.lang.OperandType;
import ghidra.program.model.listing.Data;
import ghidra.program.model.listing.Function;
import ghidra.program.model.listing.Instruction;
import ghidra.program.model.listing.InstructionIterator;
import ghidra.program.model.listing.Program;
import ghidra.program.model.scalar.Scalar;
import ghidra.util.Msg;
import ghidra.util.exception.CancelledException;
import ghidra.util.task.Task;
import ghidra.util.task.TaskMonitor;
import ghidra.util.task.WrappingTaskMonitor;
/**
* This command runs all of the <b>exact</b> {@link VTProgramCorrelator}s that return
* unique matches (i.e., only one of each match is found in each program):
* <ol>
* <li> Exact Symbol Name correlator </li>
* <li> Exact Data correlator </li>
* <li> Exact Function Byte correlator </li>
* <li> Exact Function Instruction correlator </li>
* <li> Exact Function Mnemonic correlator </li>
* </ol>
*
* <P> After running each correlator all matches are accepted since they are exact/unique matches
* and all markup from the source program functions is applied to the matching destination program
* functions.
*
* <P> Next, this command runs the Duplicate Function Instruction correlator to find any non-unique
* functions with exact instruction bytes then compares their operands to determine and accept
* correct matches with markup.
*
* <P> The command then gets a little more speculative by running the Combined Function and Data
* Reference correlator, which uses match information from the previous correlators to find more
* matches.
*
* <P> As more techniques get developed, more automation will be added to this command.
*
*/
public class AutoVersionTrackingTask extends Task {
private static final String NAME = "Auto Version Tracking Command";
private VTSession session;
private MatchInfoFactory matchInfoFactory;
private AddressCorrelatorManager addressCorrelator;
private Program sourceProgram;
private Program destinationProgram;
private AddressSetView sourceAddressSet;
private AddressSetView destinationAddressSet;
private double minCombinedReferenceCorrelatorScore;
private double minCombinedReferenceCorrelatorConfidence;
private ToolOptions applyOptions;
private String statusMsg = null;
private static int NUM_CORRELATORS = 8;
/**
* Constructor for a modal/blocking AutoVersionTrackingTask
*
* @param session The Version Tracking session containing the source, destination, correlator
* and match information needed for this command.
* @param options the options used when applying matches
* @param minCombinedReferenceCorrelatorScore The minimum score used to limit matches created by
* the Combined Reference Correlator.
* @param minCombinedReferenceCorrelatorConfidence The minimum confidence used to limit matches
* created by the Combined Reference Correlator.
*/
public AutoVersionTrackingTask(VTSession session, ToolOptions options,
double minCombinedReferenceCorrelatorScore,
double minCombinedReferenceCorrelatorConfidence) {
super(NAME, true, true, true);
this.session = session;
this.matchInfoFactory = new MatchInfoFactory();
this.addressCorrelator = new AddressCorrelatorManager(() -> session);
this.sourceProgram = session.getSourceProgram();
this.destinationProgram = session.getDestinationProgram();
this.minCombinedReferenceCorrelatorScore = minCombinedReferenceCorrelatorScore;
this.minCombinedReferenceCorrelatorConfidence = minCombinedReferenceCorrelatorConfidence;
this.applyOptions = options;
}
@Override
public int getStatusTextAlignment() {
return SwingConstants.LEADING;
}
@Override
public void run(TaskMonitor monitor) throws CancelledException {
boolean error = true;
int id = session.startTransaction(NAME);
try {
session.setEventsEnabled(false);
doRun(monitor);
error = false;
}
catch (CancelledException e) {
error = false; // allow work performed so far to be saved
}
finally {
session.setEventsEnabled(true);
session.endTransaction(id, !error);
}
}
private void doRun(TaskMonitor realMonitor) throws CancelledException {
SubTaskMonitor monitor = new SubTaskMonitor(realMonitor);
boolean hasApplyErrors = false;
sourceAddressSet = sourceProgram.getMemory().getLoadedAndInitializedAddressSet();
destinationAddressSet = destinationProgram.getMemory().getLoadedAndInitializedAddressSet();
int count = 0;
monitor.doInitialize(NUM_CORRELATORS);
// save user option and use to determine whether to handle implied matches at all later
boolean autoCreateImpliedMatches =
applyOptions.getBoolean(VTOptionDefines.AUTO_CREATE_IMPLIED_MATCH, false);
// Turn off auto implied matches and handle later if user had that option set
// This is because when run from the VT GUI action implied matches are created automatically
// by the VT controller when the option is set but they are not created when called from a
// script since there is no VT controller in that case. If allowed to happen in
// GUI then they will happen twice when called later in this task and the implied match
// votes will be wrong. This Task doesn't know if called from GUI or script so this is
// klunky but will make sure they are only processed once and will make sure the user option
// is put back the way the user had it.
applyOptions.setBoolean(VTOptionDefines.AUTO_CREATE_IMPLIED_MATCH, false);
// Use default options for all of the "exact" correlators; passed in options for the others
VTOptions options;
// Run the correlators in the following order:
// Do this one first because we don't want it to find ones that get markup applied by later
// correlators
VTProgramCorrelatorFactory factory = new SymbolNameProgramCorrelatorFactory();
options = factory.createDefaultOptions();
String prefix = "%s correlation (%d of " + NUM_CORRELATORS + ") - ";
monitor.setPrefix(String.format(prefix, "Symbol Name", ++count));
hasApplyErrors = correlateAndPossiblyApply(factory, options, monitor);
monitor.doIncrementProgress();
factory = new ExactDataMatchProgramCorrelatorFactory();
options = factory.createDefaultOptions();
monitor.setPrefix(String.format(prefix, "Exact Data", ++count));
hasApplyErrors |= correlateAndPossiblyApply(factory, options, monitor);
monitor.doIncrementProgress();
factory = new ExactMatchBytesProgramCorrelatorFactory();
options = factory.createDefaultOptions();
monitor.setPrefix(String.format(prefix, "Exact Bytes", ++count));
hasApplyErrors |= correlateAndPossiblyApply(factory, options, monitor);
monitor.doIncrementProgress();
factory = new ExactMatchInstructionsProgramCorrelatorFactory();
options = factory.createDefaultOptions();
monitor.setPrefix(String.format(prefix, "Exact Instructions", ++count));
hasApplyErrors |= correlateAndPossiblyApply(factory, options, monitor);
monitor.doIncrementProgress();
factory = new ExactMatchMnemonicsProgramCorrelatorFactory();
options = factory.createDefaultOptions();
monitor.setPrefix(String.format(prefix, "Exact Mnemonic", ++count));
hasApplyErrors |= correlateAndPossiblyApply(factory, options, monitor);
monitor.doIncrementProgress();
// This is the first of the "speculative" post-correlator match algorithm. The correlator
// returns all duplicate function instruction matches so there will always be more
// than one possible match for each function. The compare mechanism used by the
// function compare window determines matches based on matching operand values.
// Given that each function must contains the same instructions to even become a match,
// and the compare function mechanism has been very well tested, the mechanism for
// finding the correct match is very accurate.
factory = new DuplicateFunctionMatchProgramCorrelatorFactory();
options = factory.createDefaultOptions();
monitor.setPrefix(String.format(prefix, "Duplicate Function", ++count));
hasApplyErrors |= correlateAndPossiblyApplyDuplicateFunctions(factory, options, monitor);
monitor.doIncrementProgress();
// The rest are mores speculative matching algorithms because they depend on our
// choosing the correct score/confidence pair to determine very probable matches. These
// values were chosen based on what has been seen so far but this needs to be tested
// further on more programs and possibly add options for users to give their own thresholds.
// Get the names of the confidence and similarity score thresholds that
// are used by all of the "reference" correlators
String confidenceOption = VTAbstractReferenceProgramCorrelatorFactory.CONFIDENCE_THRESHOLD;
String scoreOption = VTAbstractReferenceProgramCorrelatorFactory.SIMILARITY_THRESHOLD;
// Get the number of data and function matches
int numDataMatches = getNumberOfDataMatches(monitor);
int numFunctionMatches = getNumberOfFunctionMatches(monitor);
// Run the DataReferenceCorrelator if there are accepted data matches but no accepted
// function matches
if (numDataMatches > 0 && numFunctionMatches == 0) {
factory = new DataReferenceProgramCorrelatorFactory();
options = factory.createDefaultOptions();
options.setDouble(confidenceOption, minCombinedReferenceCorrelatorConfidence);
options.setDouble(scoreOption, minCombinedReferenceCorrelatorScore);
monitor.setPrefix(String.format(prefix, "Data Reference", ++count));
hasApplyErrors = hasApplyErrors | correlateAndPossiblyApply(factory, options, monitor);
monitor.doIncrementProgress();
// Get the number of data and function matches again if this correlator ran
numDataMatches = getNumberOfDataMatches(monitor);
numFunctionMatches = getNumberOfFunctionMatches(monitor);
}
// Run the FunctionReferenceCorrelator if there are accepted function matches but no
// accepted data matches
if (numDataMatches > 0 && numFunctionMatches == 0) {
factory = new FunctionReferenceProgramCorrelatorFactory();
options = factory.createDefaultOptions();
options.setDouble(confidenceOption, minCombinedReferenceCorrelatorConfidence);
options.setDouble(scoreOption, minCombinedReferenceCorrelatorScore);
factory = new FunctionReferenceProgramCorrelatorFactory();
monitor.setPrefix(String.format(prefix, "Function Reference", ++count));
hasApplyErrors = hasApplyErrors | correlateAndPossiblyApply(factory, options, monitor);
monitor.doIncrementProgress();
// Get the number of data and function matches again if this correlator ran
numDataMatches = getNumberOfDataMatches(monitor);
numFunctionMatches = getNumberOfFunctionMatches(monitor);
}
// Run the CombinedDataAndFunctionReferenceCorrelator if there are both accepted function
// matches but and data matches
if (numDataMatches > 0 && numFunctionMatches > 0) {
factory = new CombinedFunctionAndDataReferenceProgramCorrelatorFactory();
options = factory.createDefaultOptions();
options.setDouble(confidenceOption, minCombinedReferenceCorrelatorConfidence);
options.setDouble(scoreOption, minCombinedReferenceCorrelatorScore);
monitor.setPrefix(String.format(prefix, "Function and Data", ++count));
hasApplyErrors = hasApplyErrors | correlateAndPossiblyApply(factory, options, monitor);
monitor.doIncrementProgress();
}
// if user had implied match option chosen then figure out implied matches now
// TODO: add option for applying good matches and num votes/conflicts
if (autoCreateImpliedMatches) {
hasApplyErrors = hasApplyErrors | createImpliedMatches(true, monitor);
}
String applyMarkupStatus = " with no apply markup errors.";
if (hasApplyErrors) {
applyMarkupStatus =
" with some apply markup errors. See the log or the markup table for more details";
}
statusMsg = NAME + " completed successfully" + applyMarkupStatus;
// reset auto implied match option to user choice
// TODO: make separate AutoVT implied match option
applyOptions.setBoolean(VTOptionDefines.AUTO_CREATE_IMPLIED_MATCH,
autoCreateImpliedMatches);
}
/**
* Method to create implied matches for the existing applied matches in the current session
* @param applyGoodMatches if true, create applied matches for "good" implied matches based on
* votes/conflict information. For all the applied implied matches, rerun the creation of
* applied matches until no new ones found.
* @param monitor the task monitor
* @return true if there are any apply errors, false otherwise
* @throws CancelledException if cancelled
*/
private boolean createImpliedMatches(boolean applyGoodMatches, TaskMonitor monitor)
throws CancelledException {
Set<VTAssociation> processedSrcDestPairs = new HashSet<>();
List<VTMatchSet> matchSets = session.getMatchSets();
//TODO: make these options
int minVoteCountNeeded = 2;
int maxConflictsAllowed = 0;
monitor.setMessage("Creating Implied Matches...");
monitor.initialize(matchSets.size());
// create implied matches for the existing matchSets (ie sets of results from various
// correlators
for (VTMatchSet matchSet : matchSets) {
monitor.checkCancelled();
Collection<VTMatch> matches = matchSet.getMatches();
createImpliedMatches(monitor, processedSrcDestPairs, matches);
monitor.incrementProgress();
}
// if user chose not to apply good implied matches then don't continue
if (!applyGoodMatches) {
return false;
}
// otherwise, try to find and apply good implied matches until no more to be found
boolean hasApplyErrors = false;
VTMatchSet impliedMatchSet = session.getImpliedMatchSet();
Set<VTMatch> goodImpliedMatches =
findGoodImpliedMatches(impliedMatchSet.getMatches(), minVoteCountNeeded,
maxConflictsAllowed, monitor);
while (goodImpliedMatches.size() > 0) {
monitor.checkCancelled();
// apply the "good" implied matches
hasApplyErrors |= applyMatches(goodImpliedMatches, monitor);
// possibly create more implied matches from the newly applied matches
createImpliedMatches(monitor, processedSrcDestPairs, goodImpliedMatches);
// possibly find more "good" implied matches from any new implied matches found
impliedMatchSet = session.getImpliedMatchSet();
goodImpliedMatches = findGoodImpliedMatches(impliedMatchSet.getMatches(),
minVoteCountNeeded, maxConflictsAllowed, monitor);
}
return hasApplyErrors;
}
private void createImpliedMatches(TaskMonitor monitor, Set<VTAssociation> processedSrcDestPairs,
Collection<VTMatch> matches) throws CancelledException {
for (VTMatch match : matches) {
monitor.checkCancelled();
VTAssociation association = match.getAssociation();
// Implied matches currently only created for functions so skip matches that are
// data matches
if (association.getType() == VTAssociationType.DATA) {
continue;
}
// Implied matches should only be created for matches that user has accepted as
// good matches
if (association.getStatus() != VTAssociationStatus.ACCEPTED) {
continue;
}
// only process the same match pair once so implied vote counts are not overinflated
if (processedSrcDestPairs.contains(association)) {
continue;
}
MatchInfo matchInfo = matchInfoFactory.getMatchInfo(match, addressCorrelator);
ImpliedMatchUtils.updateImpliedMatchForAcceptedAssocation(
matchInfo.getSourceFunction(),
matchInfo.getDestinationFunction(), session,
addressCorrelator, monitor);
processedSrcDestPairs.add(association);
}
}
/**
* Method to find good implied matches based on number of votes and conflicts
* @param matchesToProcess the set of matches to process for good implied matches
* @param minVoteCountNeeded the minimum vote count needed for a "good" implied match
* @param maxConflictsAllowed the maximum number of conflicts allowed for a "good" implied match
* @param monitor the monitor
* @return a set of good implied matches based on the minVoteCountNeeded needed and
* maxConfictsAllowed
* @throws CancelledException if cancelled
*/
private Set<VTMatch> findGoodImpliedMatches(Collection<VTMatch> matchesToProcess,
int minVoteCountNeeded, int maxConflictsAllowed,
TaskMonitor monitor) throws CancelledException {
Set<VTMatch> goodImpliedMatches = new HashSet<>();
for (VTMatch match : matchesToProcess) {
monitor.checkCancelled();
VTAssociation association = match.getAssociation();
// skip if already accepted or blocked match
if (association.getStatus() != VTAssociationStatus.AVAILABLE) {
continue;
}
// skip if there are any conflicting associations
int numConflicts = association.getRelatedAssociations().size() - 1;
if (numConflicts > maxConflictsAllowed) {
continue;
}
int voteCount = association.getVoteCount();
if (voteCount >= minVoteCountNeeded) {
goodImpliedMatches.add(match);
}
monitor.incrementProgress();
}
return goodImpliedMatches;
}
private int getNumberOfDataMatches(TaskMonitor monitor) throws CancelledException {
int numDataMatches = 0;
List<VTMatchSet> matchSets = session.getMatchSets();
for (VTMatchSet matchSet : matchSets) {
monitor.checkCancelled();
Collection<VTMatch> matches = matchSet.getMatches();
for (VTMatch match : matches) {
monitor.checkCancelled();
if (match.getAssociation().getStatus() == VTAssociationStatus.ACCEPTED &&
match.getAssociation().getType() == VTAssociationType.DATA) {
numDataMatches++;
}
}
}
return numDataMatches;
}
private int getNumberOfFunctionMatches(TaskMonitor monitor) throws CancelledException {
int numFunctionMatches = 0;
List<VTMatchSet> matchSets = session.getMatchSets();
for (VTMatchSet matchSet : matchSets) {
monitor.checkCancelled();
Collection<VTMatch> matches = matchSet.getMatches();
for (VTMatch match : matches) {
monitor.checkCancelled();
if (match.getAssociation().getStatus() == VTAssociationStatus.ACCEPTED &&
match.getAssociation().getType() == VTAssociationType.FUNCTION) {
numFunctionMatches++;
}
}
}
return numFunctionMatches;
}
/**
* Runs the given version tracking (VT) correlator and applies the returned matches meeting the
* given score and confidence thresholds and are not otherwise blocked.
* @param factory The correlator factory used to create and run the desired VT correlator.
* @param options The options to pass the correlator including score and confidence values.
* @param monitor Checks to see if user has cancelled.
* @throws CancelledException if cancelled
*/
private boolean correlateAndPossiblyApply(VTProgramCorrelatorFactory factory, VTOptions options,
TaskMonitor monitor) throws CancelledException {
monitor.checkCancelled();
monitor.setMessage(
"Finding and applying good " + factory.getName() + " matches and markup.");
VTProgramCorrelator correlator = factory.createCorrelator(sourceProgram, sourceAddressSet,
destinationProgram, destinationAddressSet, options);
VTMatchSet results = correlator.correlate(session, monitor);
monitor.initialize(results.getMatchCount());
boolean hasMarkupErrors = applyMatches(results.getMatches(), monitor);
monitor.incrementProgress(1);
return hasMarkupErrors;
}
/**
* Runs the Duplicate Exact Function match version tracking (VT) correlator then determines
* correct matches based on matching operand values. Those matches are accepted and other
* possible matches for those functions are blocked. Markup from accepted source functions
* is applied to matching destination functions.
*
* @param factory The correlator factory used to create and run the desired VT correlator. In
* this case, the duplicate function instruction match correlator.
* @param monitor Checks to see if user has cancelled.
* @throws CancelledException if cancelled
*/
private boolean correlateAndPossiblyApplyDuplicateFunctions(VTProgramCorrelatorFactory factory,
VTOptions options, TaskMonitor monitor) throws CancelledException {
monitor.setMessage(
"Finding and applying good " + factory.getName() + " matches and markup.");
VTProgramCorrelator correlator = factory.createCorrelator(sourceProgram, sourceAddressSet,
destinationProgram, destinationAddressSet, options);
VTMatchSet results = correlator.correlate(session, monitor);
monitor.initialize(results.getMatchCount());
boolean hasMarkupErrors = applyDuplicateFunctionMatches(results, monitor);
monitor.incrementProgress(1);
return hasMarkupErrors;
}
/**
* Called for all correlators that are run by this command except the duplicate function
* instruction match correlator.
* @param matches The set of matches to try to accept
* @param monitor the task monitor
* @return true if some matches have markup errors and false if none have markup errors
* @throws CancelledException if cancelled
*/
private boolean applyMatches(Collection<VTMatch> matches, TaskMonitor monitor)
throws CancelledException {
// If this value gets set to true then there are some markup errors in the whole set of
// matches.
boolean someMatchesHaveMarkupErrors = false;
// Note: no need to check score/confidence because they are passed into the correlator
// ahead of time so correlator only returns matches higher than given score/threshold
for (VTMatch match : matches) {
monitor.checkCancelled();
VTAssociation association = match.getAssociation();
if (!association.getStatus().canApply()) {
continue;
}
if (hasAcceptedRelatedAssociation(association, monitor)) {
Msg.warn(AutoVersionTrackingTask.class,
"This association has a related association with an accepted match so cannot " +
"make this association accepted which would try to block the already accepted " +
"related association " +
association);
continue;
}
if (!tryToSetAccepted(association)) {
continue;
}
MatchInfo matchInfo = matchInfoFactory.getMatchInfo(match, addressCorrelator);
Collection<VTMarkupItem> markupItems = matchInfo.getAppliableMarkupItems(monitor);
if (markupItems == null || markupItems.size() == 0) {
continue;
}
ApplyMarkupItemTask markupTask =
new ApplyMarkupItemTask(session, markupItems, applyOptions);
markupTask.run(monitor);
boolean currentMatchHasErrors = markupTask.hasErrors();
if (currentMatchHasErrors) {
someMatchesHaveMarkupErrors = true;
}
}
return someMatchesHaveMarkupErrors;
}
/**
* This method tries to set a match association as accepted.
* @param association The match association between two match items.
* @return true if match is accepted and false if an exception occurred and the match couldn't be
* accepted.
*/
private static boolean tryToSetAccepted(VTAssociation association) {
try {
association.setAccepted();
return true;
}
catch (VTAssociationStatusException e) {
Msg.warn(AutoVersionTrackingTask.class,
"Could not set match accepted for " + association, e);
return false;
}
}
/**
* Method to test whether any related associations (ie associations with either the same source
* or the same destination address) have already been accepted
* @param association the given association (src/dest match pair)
* @param taskMonitor the task monitor
* @return true if any related associations have already been accepted, false otherwise
* @throws CancelledException if cancelled
*/
private boolean hasAcceptedRelatedAssociation(VTAssociation association,
TaskMonitor taskMonitor) throws CancelledException {
VTAssociationManager vtAssocManager = session.getAssociationManager();
Set<VTAssociation> relatedAssociations =
new HashSet<VTAssociation>(
vtAssocManager.getRelatedAssociationsBySourceAndDestinationAddress(
association.getSourceAddress(), association.getDestinationAddress()));
for (VTAssociation relatedAssociation : relatedAssociations) {
taskMonitor.checkCancelled();
//skip self
if (relatedAssociation.equals(association)) {
continue;
}
VTAssociationStatus status = relatedAssociation.getStatus();
if (status.equals(VTAssociationStatus.ACCEPTED)) {
Msg.debug(this, relatedAssociation.toString() + " is already accepted match.");
return true;
}
}
return false;
}
/**
* Method to accept matches and apply markup for duplicate function instruction matches with
* matching operands if they are a unique match within their associated subset. To explain in
* more depth, the duplicate function instruction correlator returns a set of function matches
* such that there are subsets of matches where each function pair has the same exact function
* instructions but possibly different operands. Also, there must be more than one possible
* function pair association or it would have been identified as a unique match by the exact
* unique function instruction correltor. This method attempts to find unique matches from
* within the related subsets by comparing operand information.
* @param matches The set of matches from the duplicate function instruction correlator
* @param monitor Allows user to cancel
* @return true if there are any markup errors, false if no markup errors
* @throws CancelledException if cancelled
*/
private boolean applyDuplicateFunctionMatches(VTMatchSet matchSet, TaskMonitor monitor)
throws CancelledException {
Collection<VTMatch> matches = matchSet.getMatches();
// If this value gets set to true later it indicates markup errors upon applying markup.
boolean someMatchesHaveMarkupErrors = false;
Set<VTAssociation> processedSrcDestPairs = new HashSet<>();
String message = "Processing match %d of %d...";
int n = matches.size();
Iterator<VTMatch> it = matches.iterator();
for (int i = 0; it.hasNext(); i++) {
monitor.checkCancelled();
monitor.setMessage(String.format(message, i, n));
VTMatch match = it.next();
VTAssociation association = match.getAssociation();
// skip if match has already been processed (ie matched or determined to be unable
// to match)
if (processedSrcDestPairs.contains(association)) {
continue;
}
// if this association src/dest pair is already matched or blocked skip it
if (association.getStatus() != VTAssociationStatus.AVAILABLE) {
processedSrcDestPairs.add(association);
continue;
}
// get the entire set of functions with the same instructions as the given source and
// destination pair
Set<VTAssociation> allRelatedAssociations = getAllRelatedAssociations(
match.getSourceAddress(), match.getDestinationAddress(), monitor);
// Try to find all the unique matches in this set with the same operands as each other.
// The duplicate function instruction correlator already grouped them into sets of
// functions pairs with exactly the same instructions. This is trying to find the
// correct matches in this set.
Collection<VTAssociation> uniqueAssociations =
findUniqueAssociations(allRelatedAssociations, monitor);
// Whether or not a unique association has been found, add these associations to the
// processed list so the check is not repeated for another src/dest pair in this
// set later.
processedSrcDestPairs.addAll(allRelatedAssociations);
if (uniqueAssociations == null) {
continue;
}
// For each good match found, accept the match and apply markup
for (VTAssociation uniqueAssociation : uniqueAssociations) {
monitor.checkCancelled();
VTMatch theMatch =
getAssociationMatchFromMatchSet(uniqueAssociation, matchSet, monitor);
if (theMatch == null) {
Msg.error(this,
uniqueAssociation.toString() + " Should be in the original match set used");
continue;
}
someMatchesHaveMarkupErrors |= tryToAcceptMatchAndApplyMarkup(theMatch, monitor);
}
}
return someMatchesHaveMarkupErrors;
}
/**
* Get the entire set of related duplicate functions with the same instructions
* @param source the given source address
* @param destination the given destination address
* @param monitor the task monitor
* @return the entire set of related duplicate functions with the same instructions
* @throws CancelledException if cancelled
*/
private Set<VTAssociation> getAllRelatedAssociations(Address source, Address destination,
TaskMonitor monitor) throws CancelledException {
// get all associations with the same source or the same destination address
VTAssociationManager vtAssocManager = session.getAssociationManager();
Collection<VTAssociation> relatedAssociations =
vtAssocManager.getRelatedAssociationsBySourceAndDestinationAddress(
source, destination);
Set<VTAssociation> allRelatedAssociations = new HashSet<VTAssociation>(relatedAssociations);
// from the initial set of related associations get all the other ones that have related
// associations with all the source/destinations of the newly found associations
for (VTAssociation association : relatedAssociations) {
monitor.checkCancelled();
allRelatedAssociations
.addAll(vtAssocManager.getRelatedAssociationsBySourceAndDestinationAddress(
association.getSourceAddress(), association.getDestinationAddress()));
}
return allRelatedAssociations;
}
/**
* Given an association, get the VTMatch from the given matchSet (ie set of matches from a
* particular correlator). There may be multiple correlators that have found the same match.
* This is making sure the match is from the desired correlator.
* @param association the given association
* @param matchSet the given correlator matchSet
* @param monitor the task monitor
* @return the match with same source and destination addresss as the given association from the
* given correlator's set of matches.
* @throws CancelledException if cancelled
*/
private VTMatch getAssociationMatchFromMatchSet(VTAssociation association,
VTMatchSet matchSet, TaskMonitor monitor) throws CancelledException {
List<VTMatch> assocMatchesInMatchSet = new ArrayList<VTMatch>();
List<VTMatch> assocationMatches = session.getMatches(association);
Collection<VTMatch> matchSetMatches = matchSet.getMatches();
for (VTMatch match : assocationMatches) {
monitor.checkCancelled();
if (matchSetMatches.contains(match)) {
assocMatchesInMatchSet.add(match);
}
}
if (assocMatchesInMatchSet.size() == 1) {
return assocMatchesInMatchSet.get(0);
}
Msg.error(this,
"Expected single match in matchset for association " + association.toString());
return null;
}
/**
* From the given related association, ie a group of src/dest pairs of functions with identical
* instructions, use operand information to find any unique matches in the set.
* @param relatedAssociations group of src/dest pairs of functions with identical instructions
* @param monitor the task monitor
* @return a list of src/destination associations that are uniquely matched based on matching
* operands
* @throws CancelledException if cancelled
*/
private List<VTAssociation> findUniqueAssociations(
Collection<VTAssociation> relatedAssociations, TaskMonitor monitor)
throws CancelledException {
// create function to operand map maps for each source and destination function
// in the given related associations (src/dst function pairs)
Map<Function, Map<Long, Map<Integer, Object>>> sourceFunctionsMap =
createFunctionsMap(relatedAssociations, true, monitor);
Map<Function, Map<Long, Map<Integer, Object>>> destFunctionsMap =
createFunctionsMap(relatedAssociations, false, monitor);
// only functions with scalar or address operands are mapped so the lists could be
// empty if there are functions with no operand info to be mapped
if (sourceFunctionsMap.isEmpty() || destFunctionsMap.isEmpty()) {
return null;
}
List<VTAssociation> uniqueAssociations = findUniqueAssociationsUsingMaps(sourceFunctionsMap,
destFunctionsMap, monitor);
return uniqueAssociations;
}
/**
* Method to use the given function to operand maps, for sets of source and destination functions
* with identical instructions, to identify any unique src/dst matches within the set.
* instructions
* @param sourceFunctionsMap the source functions map
* @param destFunctionsMap the destination functions map
* @param monitor the task monitor
* @return the list of unique associations (src/dest function pairs) if any
* @throws CancelledException if cancelled
*/
private List<VTAssociation> findUniqueAssociationsUsingMaps(
Map<Function, Map<Long, Map<Integer, Object>>> sourceFunctionsMap,
Map<Function, Map<Long, Map<Integer, Object>>> destFunctionsMap,
TaskMonitor monitor)
throws CancelledException {
List<VTAssociation> uniqueAssociations = new ArrayList<VTAssociation>();
// for each source function, try to find a single matching destination function from
// the associated functions that have map info
VTAssociationManager vtAssocManager = session.getAssociationManager();
Set<Function> sourceFunctions = sourceFunctionsMap.keySet();
Set<Function> matchedDestFunctions = new HashSet<Function>();
for (Function sourceFunction : sourceFunctions) {
monitor.checkCancelled();
Map<Long, Map<Integer, Object>> sourceFunctionMap =
sourceFunctionsMap.get(sourceFunction);
Function destFunction =
getSingleMatch(sourceFunctionMap, destFunctionsMap, matchedDestFunctions, monitor);
if (destFunction == null) {
continue;
}
// track matched destination functions so they are not checked again later
matchedDestFunctions.add(destFunction);
// add the association for the given src/dest pair to the list of good matches
VTAssociation association = vtAssocManager
.getAssociation(sourceFunction.getEntryPoint(), destFunction.getEntryPoint());
if (association != null) {
uniqueAssociations.add(association);
}
}
return uniqueAssociations;
}
/**
* Create an operand map for each source or destination function in the given associations
* @param associations The collection of associations (src/dest function pairs)
* @param source if true use the source function, if false use the destination function
* @param monitor the task monitor
* @return the map of functions to their operand maps
* @throws CancelledException if cancelled
*/
private Map<Function, Map<Long, Map<Integer, Object>>> createFunctionsMap(
Collection<VTAssociation> associations, boolean source, TaskMonitor monitor)
throws CancelledException {
Map<Function, Map<Long, Map<Integer, Object>>> functionsMap =
new HashMap<>();
// to keep track of which functions are attempted so only mapped once since there are
// multiple pairs with same source function and multiple with the same dest function
Set<Function> functionsMapAttempted = new HashSet<Function>();
// make an operand map for each source and destination function in the given associations
for (VTAssociation association : associations) {
monitor.checkCancelled();
Function function = null;
if (source) {
function = getSourceFunction(association);
}
else {
function = getDestFunction(association);
}
if (function == null) {
continue;
}
if (functionsMapAttempted.contains(function)) {
continue;
}
functionsMapAttempted.add(function);
// create offset/operand info map for the given source function
Map<Long, Map<Integer, Object>> map =
mapFunctionScalarAndAddressOperands(function, monitor);
// only keep the ones with operand info to map
if (map != null) {
functionsMap.put(function, map);
}
}
return functionsMap;
}
/**
* Using the given source function's map and a list of destination function maps, and a list
* of destination functions to omit because they already have found matches, try to find a
* single match using matching operand info.
*
* @param sourceFunctionMap the operand map for the source function
* @param destFunctionsMap the maps for the destination functions
* @param destFunctionsToOmit the destination functions that already have been mapped
* @param monitor the task monitor
* @return a single matching destination function or null if none or more than one are found
* @throws CancelledException if cancelled
*/
private Function getSingleMatch(Map<Long, Map<Integer, Object>> sourceFunctionMap,
Map<Function, Map<Long, Map<Integer, Object>>> destFunctionsMap,
Set<Function> destFunctionsToOmit,
TaskMonitor monitor) throws CancelledException {
Set<Function> destFunctions = destFunctionsMap.keySet();
Set<Function> matchingFunctions = new HashSet<>();