/*
Patchdiff2
Portions (C) 2010 - 2011 Nicolas Pouvesle
Portions (C) 2007 - 2009 Tenable Network Security, Inc.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License version 2 as
published by the Free Software Foundation.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see .
*/
#include "precomp.hpp"
#include "hash.hpp"
#include "sig.hpp"
#include "diff.hpp"
#include "clist.hpp"
#include "display.hpp"
#include "backup.hpp"
#include "options.hpp"
/*------------------------------------------------*/
/* function : diff_init_hash */
/* description: Initializes a hash structure and */
/* creates successor xrefs */
/*------------------------------------------------*/
static hpsig_t * diff_init_hash(slist_t * sl)
{
fref_t * fref;
psig_t * sig;
hpsig_t * h;
size_t i;
h = hash_init(sl->num);
if (!h) return NULL;
for(i=0; inum; i++)
{
if (hash_add_ea(h, sl->sigs[i]) < 0)
{
hash_free(h);
return NULL;
}
}
// adds xrefs
for(i=0; inum; i++)
{
if (sl->sigs[i]->srefs)
{
fref = sl->sigs[i]->srefs->list;
while (fref)
{
if (!fref->rtype)
{
sig = hash_find_ea(h, fref->ea);
if (sig)
sig_add_pref(sig, sl->sigs[i]->startEA, fref->type, DO_NOT_CHECK_REF);
}
fref = fref->next;
}
}
if (sl->sigs[i]->prefs)
{
fref = sl->sigs[i]->prefs->list;
while (fref)
{
if (!fref->rtype)
{
sig = hash_find_ea(h, fref->ea);
if (sig)
sig_add_sref(sig, sl->sigs[i]->startEA, fref->type, DO_NOT_CHECK_REF);
}
fref = fref->next;
}
}
}
return h;
}
/*------------------------------------------------*/
/* function : slist_init_crefs */
/* description: Initializes slist crefs */
/*------------------------------------------------*/
static int slist_init_crefs(slist_t * l)
{
hpsig_t * h = NULL;
clist_t * cl1, * cl2;
size_t i;
h = diff_init_hash(l);
if(!h) return -1;
for (i=0; inum; i++)
{
cl1 = clist_init_from_refs(h, sig_get_preds(l->sigs[i]));
cl2 = clist_init_from_refs(h, sig_get_succs(l->sigs[i]));
sig_set_crefs(l->sigs[i], SIG_PRED, cl1);
sig_set_crefs(l->sigs[i], SIG_SUCC, cl2);
}
return 0;
}
/*------------------------------------------------*/
/* function : diff_engine_initialize */
/* description: Initializes engine structures */
/*------------------------------------------------*/
static deng_t * diff_engine_initialize(slist_t * l1, slist_t * l2, options_t * opt)
{
deng_t * eng;
if (slist_init_crefs(l1) != 0) return NULL;
if (slist_init_crefs(l2) != 0) return NULL;
eng = (deng_t *)qalloc(sizeof(*eng));
if (!eng) return NULL;
eng->magic = 0x0BADF00D;
eng->wnum = 0;
eng->identical = 0;
eng->matched = 0;
eng->unmatched = l1->num + l2->num;
eng->opt = opt;
return eng;
}
/*------------------------------------------------*/
/* function : diff_engine_initialize */
/* description: Initializes engine structures */
/*------------------------------------------------*/
void diff_engine_free(deng_t * eng)
{
if (eng->ilist) siglist_free(eng->ilist);
if (eng->mlist) siglist_free(eng->mlist);
if (eng->ulist) siglist_free(eng->ulist);
qfree(eng);
}
/*------------------------------------------------*/
/* function : sig_equal */
/* description: Checks if 2 sigs are equal */
/*------------------------------------------------*/
bool sig_equal(psig_t * s1, psig_t * s2, int type)
{
if (s1->sig != s2->sig || s1->hash != s2->hash)
return false;
if (type == DIFF_EQUAL_SIG_HASH_CRC_STR)
{
if (s1->str_hash != s2->str_hash)
return false;
}
if (type crc_hash != s2->crc_hash)
return false;
}
return true;
}
/*------------------------------------------------*/
/* function : sig_name_equal */
/* description: Checks if 2 sig names are equal */
/*------------------------------------------------*/
static bool sig_name_equal(psig_t * s1, psig_t * s2)
{
if (!strncmp(s1->name, "sub_", 4) || strcmp(s1->name, s2->name))
return false;
return true;
}
/*------------------------------------------------*/
/* function : clist_equal_match */
/* description: Checks if all the elements of a */
/* clist match */
/*------------------------------------------------*/
static bool clist_equal_match(clist_t * cl1, clist_t * cl2)
{
dpsig_t * s1, * s2;
size_t i;
if (!cl1 || !cl2 || cl1->nmatch == 0 || cl2->nmatch == 0)
return false;
if (cl1->nmatch != cl2->nmatch)
return false;
s1 = cl1->msigs;
s2 = cl2->msigs;
for (i=0; inmatch; i++)
{
if ((sig_get_matched_type(s1->sig) == DIFF_UNMATCHED) || (s1->sig->msig->startEA != s2->sig->startEA))
return false;
s1 = s1->next;
s2 = s2->next;
}
return true;
}
/*------------------------------------------------*/
/* function : clist_almost_equal_match */
/* description: Checks if at lest one element of a*/
/* clist match */
/*------------------------------------------------*/
static bool clist_almost_equal_match(clist_t * cl1, clist_t * cl2)
{
dpsig_t * s1, * s2;
size_t i, k;
if (!cl1 || !cl2 || cl1->nmatch == 0 || cl2->nmatch == 0)
return false;
if (cl1->nmatch != cl2->nmatch)
return false;
s1 = cl1->msigs;
for (i=0; inmatch; i++)
{
s2 = cl2->msigs;
for (k=0; knmatch; k++)
{
if (s1->sig->msig->startEA == s2->sig->startEA)
return true;
s2 = s2->next;
}
s1 = s1->next;
}
return false;
}
/*------------------------------------------------*/
/* function : clist_get_unique_sig */
/* description: Returns first unique signature in */
/* list starting at ds */
/* note: changes ds if ds already matched */
/*------------------------------------------------*/
static dpsig_t * clist_get_unique_sig(clist_t * cl, dpsig_t ** ds, int type)
{
dpsig_t * ptr, * tmp;
if (!*ds) return NULL;
ptr = *ds;
// do not keep the current signature if not unique
while (ptr)
{
if (sig_get_matched_type(ptr->sig) != DIFF_UNMATCHED)
{
if (ptr == *ds)
{
*ds = ptr->next;
if (!*ds) return NULL;
}
tmp = ptr->next;
clist_remove(cl, ptr);
ptr = tmp;
}
else
{
if (!ptr->next) break;
if (type == DIFF_NEQUAL_SUCC)
{
if (sig_equal(ptr->sig, (*ds)->sig, type) && sig_equal(ptr->next->sig, (*ds)->sig, type))
return NULL;
if (( (!sig_equal(ptr->next->sig, (*ds)->sig, type) && (!ptr->prev || !sig_equal(ptr->prev->sig, (*ds)->sig, type))) || !clist_equal_match((*ds)->sig->cs, ptr->next->sig->cs)) && ptr->sig->cs->nmatch > 0 && ptr->sig->cs->num == ptr->sig->cs->nmatch)
break;
}
else if (type == DIFF_NEQUAL_PRED)
{
if (sig_equal(ptr->sig, (*ds)->sig, type) && sig_equal(ptr->next->sig, (*ds)->sig, type))
return NULL;
if (( (!sig_equal(ptr->next->sig, (*ds)->sig, type) && (!ptr->prev || !sig_equal(ptr->prev->sig, (*ds)->sig, type))) || !clist_equal_match((*ds)->sig->cp, ptr->next->sig->cp)) && ptr->sig->cp->nmatch > 0 && ptr->sig->cp->num == ptr->sig->cp->nmatch)
break;
}
else if (type == DIFF_EQUAL_NAME)
{
if (!sig_equal(ptr->next->sig, (*ds)->sig, type) || !sig_name_equal((*ds)->sig, ptr->next->sig))
break;
}
else if (type == DIFF_NEQUAL_STR)
{
bool b = false;
tmp = *ds;
if (ptr->sig->str_hash != 0)
{
// slow: need to improve
while (tmp)
{
if (tmp->sig->startEA != ptr->sig->startEA && tmp->sig->str_hash == ptr->sig->str_hash)
{
b = true;
break;
}
tmp = tmp->next;
}
if (!b)
break;
}
}
else
{
bool b = sig_equal(ptr->next->sig, (*ds)->sig, type);
if (!b) break;
}
ptr = ptr->next;
}
}
return ptr;
}
/*------------------------------------------------*/
/* function : clist_get_best_sig */
/* description: Returns best unique signature in */
/* list */
/* note: position pointer is incremented to the */
/* next signature in the list */
/*------------------------------------------------*/
static dpsig_t * clist_get_best_sig(clist_t * cl, int type)
{
dpsig_t * best, * ptr;
best = cl->pos;
ptr = clist_get_unique_sig(cl, &best, type);
// no more signature
if (!best) return NULL;
if (ptr == best)
{
cl->pos = best->next;
return best;
}
cl->pos = ptr;
return clist_get_best_sig(cl, type);
}
/*------------------------------------------------*/
/* function : clist_get_eq_sig */
/* description: Returns signature if sig presents */
/* in list and unique */
/*------------------------------------------------*/
static dpsig_t * clist_get_eq_sig(clist_t * cl, dpsig_t * dsig, int type)
{
dpsig_t * ds, * ptr;
bool b2, b1 = sig_is_class(dsig->sig);
ds = cl->sigs;
while (ds)
{
if (type == DIFF_NEQUAL_SUCC)
{
ptr = clist_get_unique_sig(cl, &ds, type);
if (!ds || !ptr) return NULL;
b2 = sig_is_class(ptr->sig);
if (b1 ^ b2) return NULL;
if (clist_equal_match(ptr->sig->cs, dsig->sig->cs))
{
if (ptr->next && (ptr->next->sig->sig == ptr->sig->sig || clist_equal_match(ptr->next->sig->cs, dsig->sig->cs)))
return NULL;
return ptr;
}
}
else if (type == DIFF_NEQUAL_PRED )
{
ptr = clist_get_unique_sig(cl, &ds, type);
if (!ds || !ptr) return NULL;
b2 = sig_is_class(ptr->sig);
if (b1 ^ b2) return NULL;
if (clist_equal_match(ptr->sig->cp, dsig->sig->cp))
{
if (ptr->next && (ptr->next->sig->sig == ptr->sig->sig || clist_equal_match(ptr->next->sig->cp, dsig->sig->cp)))
return NULL;
return ptr;
}
}
else if (type == DIFF_EQUAL_NAME)
{
ptr = clist_get_unique_sig(cl, &ds, type);
if (!ds || !ptr) return NULL;
if (sig_name_equal(ptr->sig, dsig->sig))
return ptr;
}
else if (type == DIFF_NEQUAL_STR)
{
ptr = clist_get_unique_sig(cl, &ds, type);
if (!ds || !ptr) return NULL;
if (ptr->sig->str_hash != 0 && ptr->sig->str_hash == dsig->sig->str_hash)
return ptr;
}
else
{
if (sig_equal(ds->sig, dsig->sig, type))
{
ptr = clist_get_unique_sig(cl, &ds, type);
if (!ds) return NULL;
if (ptr != ds || !sig_equal(ds->sig, dsig->sig, type))
return NULL;
return ds;
}
else if (ds->sig->sig < dsig->sig->sig)
{
return NULL;
}
}
ds = ds->next;
}
return NULL;
}
static void clist_update_crefs(clist_t * cl, dpsig_t * ds, int type)
{
dpsig_t * tmp, * next;
dpsig_t * tmp2, * next2;
clist_t * tcl;
tmp = cl->sigs;
while(tmp)
{
next = tmp->next;
if (type == SIG_SUCC)
tcl = tmp->sig->cs;
else
tcl = tmp->sig->cp;
tmp2 = tcl->sigs;
while(tmp2)
{
next2 = tmp2->next;
if (tmp2->sig->startEA == ds->sig->startEA)
clist_remove(tcl, tmp2);
tmp2 = next2;
}
tmp = next;
}
}
static void clist_update_and_remove(clist_t * cl, dpsig_t * ds)
{
if (ds->removed)
return;
clist_update_crefs(ds->sig->cp, ds, SIG_SUCC);
clist_update_crefs(ds->sig->cs, ds, SIG_PRED);
clist_remove(cl, ds);
}
/*------------------------------------------------*/
/* function : diff_run */
/* description: Runs binary analysis */
/*------------------------------------------------*/
static int diff_run(deng_t * eng, clist_t * cl1, clist_t * cl2, int min_type, int max_type, bool pclass)
{
dpsig_t * dsig, * dsig2;
int changed = 0;
int type = min_type;
int mtype = max_type;
bool b;
if (pclass && max_type > DIFF_EQUAL_SIG_HASH)
mtype = DIFF_EQUAL_SIG_HASH;
do
{
clist_reset(cl1);
clist_reset(cl2);
changed = 0;
while ( (dsig = clist_get_best_sig(cl1, type)) != NULL)
{
clist_reset(cl2);
dsig2 = clist_get_eq_sig(cl2, dsig, type);
if (dsig2)
{
sig_set_matched_sig(dsig->sig, dsig2->sig, type);
eng->unmatched -= 2;
if (dsig->sig->hash2 == dsig2->sig->hash2 || sig_equal(dsig->sig, dsig2->sig, DIFF_EQUAL_SIG_HASH))
eng->identical++;
else
eng->matched++;
changed = 1;
clist_update_and_remove(cl1, dsig);
clist_update_and_remove(cl2, dsig2);
b = sig_is_class(dsig->sig);
// string matching is not 100% reliable so we only match on crc/hash
if (mtype == DIFF_NEQUAL_STR)
b = true;
diff_run(eng, sig_get_crefs(dsig->sig, SIG_PRED), sig_get_crefs(dsig2->sig, SIG_PRED), min_type, max_type, b);
diff_run(eng, sig_get_crefs(dsig->sig, SIG_SUCC), sig_get_crefs(dsig2->sig, SIG_SUCC), min_type, max_type, b);
}
}
if (changed == 0)
type++;
} while(type mlist = siglist_init(eng->matched, file);
eng->ulist = siglist_init(eng->unmatched, file);
eng->ilist = siglist_init(eng->identical, file);
un1 = un2 = idf = mf = 0;
for (size_t i=0; inum; i++)
{
if (sig_is_class(l1->sigs[i]))
{
sig_free(l1->sigs[i]);
continue;
}
if (sig_get_matched_type(l1->sigs[i]) == DIFF_UNMATCHED)
{
sig_set_nfile(l1->sigs[i], 1);
siglist_add(eng->ulist, l1->sigs[i]);
un1++;
}
else
{
if (l1->sigs[i]->hash2 == l1->sigs[i]->msig->hash2 || sig_equal(l1->sigs[i], l1->sigs[i]->msig, DIFF_EQUAL_SIG_HASH))
{
siglist_add(eng->ilist, l1->sigs[i]);
idf++;
}
else
{
siglist_add(eng->mlist, l1->sigs[i]);
mf++;
}
}
}
for (size_t i=0; inum; i++)
{
if (sig_is_class(l2->sigs[i]))
{
sig_free(l2->sigs[i]);
continue;
}
if (sig_get_matched_type(l2->sigs[i]) == DIFF_UNMATCHED)
{
sig_set_nfile(l2->sigs[i], 2);
siglist_add(eng->ulist, l2->sigs[i]);
un2++;
}
}
msg("Identical functions: %d\n", idf);
msg("Matched functions: %d\n", mf);
msg("Unmatched functions 1: %d\n", un1);
msg("Unmatched functions 2: %d\n", un2);
display_results(eng);
}
if (d)
*d = eng;
return 0;
}