← Back to branch summary

~ubuntu-branches/ubuntu/breezy/clamav/breezy-backports

« back to all changes in this revision

Viewing changes to libclamav/matcher-ac.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen Gran
  • Date: 2005-09-19 09:05:59 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20050919090559-hikpqduq8yx5qxo2
Tags: 0.87-1
http://bugs.debian.org/328660
http://bugs.debian.org/323132
http://bugs.debian.org/327707
http://bugs.debian.org/328912
* New upstream version
  - Fixes CAN-2005-2920 and CAN-2005-2919 (closes: #328660)
* New logcheck line for clamav-daemon (closes: #323132)
* relibtoolize and apply kfreebsd patch (closes: #327707)
* Make sure init.d script starts freshclam up again after upgrade when run
  from if-up.d (closes: #328912)

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/matcher-ac.c
 
1
/*
 
2
 *  C implementation of the Aho-Corasick pattern matching algorithm. It's based
 
3
 *  on the ScannerDaemon's version (coded in Java) by Kurt Huwig and
 
4
 *  http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC.html
 
5
 *  Thanks to Kurt Huwig for pointing me to this page.
 
6
 *
 
7
 *  Copyright (C) 2002 - 2005 Tomasz Kojm <tkojm@clamav.net>
 
8
 *
 
9
 *  This program is free software; you can redistribute it and/or modify
 
10
 *  it under the terms of the GNU General Public License as published by
 
11
 *  the Free Software Foundation; either version 2 of the License, or
 
12
 *  (at your option) any later version.
 
13
 *
 
14
 *  This program is distributed in the hope that it will be useful,
 
15
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
16
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
17
 *  GNU General Public License for more details.
 
18
 *
 
19
 *  You should have received a copy of the GNU General Public License
 
20
 *  along with this program; if not, write to the Free Software
 
21
 *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
22
 */
 
23
 
 
24
#if HAVE_CONFIG_H
 
25
#include "clamav-config.h"
 
26
#endif
 
27
 
 
28
#include <stdio.h>
 
29
#include <string.h>
 
30
#include <stdlib.h>
 
31
#include <unistd.h>
 
32
 
 
33
#include "clamav.h"
 
34
#include "others.h"
 
35
#include "matcher.h"
 
36
#include "matcher-ac.h"
 
37
#include "defaults.h"
 
38
#include "filetypes.h"
 
39
 
 
40
#define AC_MIN_LENGTH 2
 
41
 
 
42
struct nodelist {
 
43
    struct cli_ac_node *node;
 
44
    struct nodelist *next;
 
45
};
 
46
 
 
47
int cli_ac_addpatt(struct cl_node *root, struct cli_ac_patt *pattern)
 
48
{
 
49
        struct cli_ac_node *pos, *next;
 
50
        int i;
 
51
 
 
52
    if(pattern->length < AC_MIN_LENGTH)
 
53
        return CL_EPATSHORT;
 
54
 
 
55
    pos = root->ac_root;
 
56
 
 
57
    for(i = 0; i < AC_MIN_LENGTH; i++) {
 
58
        next = pos->trans[((unsigned char) pattern->pattern[i]) & 0xff]; 
 
59
 
 
60
        if(!next) {
 
61
            next = (struct cli_ac_node *) cli_calloc(1, sizeof(struct cli_ac_node));
 
62
            if(!next) {
 
63
                cli_dbgmsg("Unable to allocate pattern node (%d)\n", sizeof(struct cl_node));
 
64
                return CL_EMEM;
 
65
            }
 
66
 
 
67
            root->ac_nodes++;
 
68
            root->ac_nodetable = (struct cli_ac_node **) cli_realloc(root->ac_nodetable, (root->ac_nodes) * sizeof(struct cli_ac_node *));
 
69
            if(root->ac_nodetable == NULL) {
 
70
                cli_dbgmsg("Unable to realloc nodetable (%d)\n", (root->ac_nodes) * sizeof(struct cl_node *));
 
71
                return CL_EMEM;
 
72
            }
 
73
            root->ac_nodetable[root->ac_nodes - 1] = next;
 
74
 
 
75
            pos->trans[((unsigned char) pattern->pattern[i]) & 0xff] = next;
 
76
        }
 
77
 
 
78
        pos = next;
 
79
    }
 
80
 
 
81
    pos->islast = 1;
 
82
 
 
83
    pattern->next = pos->list;
 
84
    pos->list = pattern;
 
85
 
 
86
    return 0;
 
87
}
 
88
 
 
89
static int cli_enqueue(struct nodelist **bfs, struct cli_ac_node *n)
 
90
{
 
91
        struct nodelist *new;
 
92
 
 
93
    new = (struct nodelist *) cli_calloc(1, sizeof(struct nodelist));
 
94
    if (new == NULL) {
 
95
        cli_dbgmsg("Unable to allocate node list (%d)\n", sizeof(struct nodelist));
 
96
        return CL_EMEM;
 
97
    }
 
98
 
 
99
    new->next = *bfs;
 
100
    new->node = n;
 
101
    *bfs = new;
 
102
    return 0;
 
103
}
 
104
 
 
105
static struct cli_ac_node *cli_dequeue(struct nodelist **bfs)
 
106
{
 
107
        struct nodelist *handler, *prev = NULL;
 
108
        struct cli_ac_node *pt;
 
109
 
 
110
    handler = *bfs;
 
111
 
 
112
    while(handler && handler->next) {
 
113
        prev = handler;
 
114
        handler = handler->next;
 
115
    }
 
116
 
 
117
    if(!handler) {
 
118
        return NULL;
 
119
    } else {
 
120
        pt = handler->node;
 
121
        free(handler);
 
122
        if(prev)
 
123
            prev->next = NULL;
 
124
        else
 
125
            *bfs = NULL;
 
126
 
 
127
        return pt;
 
128
    }
 
129
}
 
130
 
 
131
static int cli_maketrans(struct cl_node *root)
 
132
{
 
133
        struct nodelist *bfs = NULL;
 
134
        struct cli_ac_node *ac_root = root->ac_root, *child, *node;
 
135
        int i, ret;
 
136
 
 
137
 
 
138
    ac_root->fail = NULL;
 
139
    if((ret = cli_enqueue(&bfs, ac_root)) != 0) {
 
140
        return ret;
 
141
    }
 
142
 
 
143
    while((node = cli_dequeue(&bfs))) {
 
144
        if(node->islast)
 
145
            continue;
 
146
 
 
147
        for(i = 0; i < 256; i++) {
 
148
            child = node->trans[i];
 
149
            if(!child) {
 
150
                if(node->fail)
 
151
                    node->trans[i] = (node->fail)->trans[i];
 
152
                else
 
153
                    node->trans[i] = ac_root;
 
154
            } else {
 
155
                if(node->fail)
 
156
                    child->fail = (node->fail)->trans[i];
 
157
                else
 
158
                    child->fail = ac_root;
 
159
 
 
160
                if((ret = cli_enqueue(&bfs, child)) != 0) {
 
161
                    return ret;
 
162
                }
 
163
            }
 
164
        }
 
165
    }
 
166
    return 0;
 
167
}
 
168
 
 
169
int cli_ac_buildtrie(struct cl_node *root)
 
170
{
 
171
        int ret;
 
172
 
 
173
    if(!root)
 
174
        return CL_EMALFDB;
 
175
 
 
176
    if(!root->ac_root) {
 
177
        cli_dbgmsg("Pattern matcher not initialised\n");
 
178
        return 0;
 
179
    }
 
180
 
 
181
    if((ret = cli_addtypesigs(root)))
 
182
        return ret;
 
183
 
 
184
    return cli_maketrans(root);
 
185
}
 
186
 
 
187
static void cli_freepatt(struct cli_ac_patt *list)
 
188
{
 
189
        struct cli_ac_patt *handler, *prev;
 
190
        int i;
 
191
 
 
192
 
 
193
    handler = list;
 
194
 
 
195
    while(handler) {
 
196
        free(handler->pattern);
 
197
        free(handler->virname);
 
198
        if(handler->offset && (!handler->sigid || handler->partno == 1))
 
199
            free(handler->offset);
 
200
        if(handler->alt) {
 
201
            free(handler->altn);
 
202
            for(i = 0; i < handler->alt; i++)
 
203
                free(handler->altc[i]);
 
204
            free(handler->altc);
 
205
        }
 
206
        prev = handler;
 
207
        handler = handler->next;
 
208
        free(prev);
 
209
    }
 
210
}
 
211
 
 
212
void cli_ac_free(struct cl_node *root)
 
213
{
 
214
        unsigned int i;
 
215
 
 
216
 
 
217
    for(i = 0; i < root->ac_nodes; i++) {
 
218
        cli_freepatt(root->ac_nodetable[i]->list);
 
219
        free(root->ac_nodetable[i]);
 
220
    }
 
221
 
 
222
    if(root->ac_nodetable)
 
223
        free(root->ac_nodetable);
 
224
 
 
225
    if(root->ac_root)
 
226
        free(root->ac_root);
 
227
}
 
228
 
 
229
inline static int cli_findpos(const char *buffer, int offset, int length, const struct cli_ac_patt *pattern)
 
230
{
 
231
        int bufferpos = offset + AC_MIN_LENGTH;
 
232
        int postfixend = offset + length;
 
233
        unsigned int i, j, alt = 0, found = 0;
 
234
 
 
235
 
 
236
    if(bufferpos >= length)
 
237
        bufferpos %= length;
 
238
 
 
239
    for(i = AC_MIN_LENGTH; i < pattern->length; i++) {
 
240
 
 
241
        if(bufferpos == postfixend)
 
242
            return 0;
 
243
 
 
244
        if(pattern->pattern[i] == CLI_ALT) {
 
245
            for(j = 0; j < pattern->altn[alt]; j++) {
 
246
                if(pattern->altc[alt][j] == buffer[bufferpos])
 
247
                    found = 1;
 
248
            }
 
249
 
 
250
            if(!found)
 
251
                return 0;
 
252
            alt++;
 
253
 
 
254
        } else if(pattern->pattern[i] != CLI_IGN && (char) pattern->pattern[i] != buffer[bufferpos])
 
255
            return 0;
 
256
 
 
257
        bufferpos++;
 
258
 
 
259
        if(bufferpos == length)
 
260
            bufferpos = 0;
 
261
    }
 
262
 
 
263
    return 1;
 
264
}
 
265
 
 
266
int cli_ac_scanbuff(const char *buffer, unsigned int length, const char **virname, const struct cl_node *root, int *partcnt, short otfrec, unsigned long int offset, unsigned long int *partoff, unsigned short ftype, int fd)
 
267
{
 
268
        struct cli_ac_node *current;
 
269
        struct cli_ac_patt *pt;
 
270
        int position, type = CL_CLEAN, dist, t;
 
271
        unsigned int i;
 
272
 
 
273
 
 
274
    if(!root->ac_root)
 
275
        return CL_CLEAN;
 
276
 
 
277
    if(!partcnt || !partoff) {
 
278
        cli_dbgmsg("cli_ac_scanbuff(): partcnt == NULL || partoff == NULL\n");
 
279
        return CL_ENULLARG;
 
280
    }
 
281
 
 
282
    current = root->ac_root;
 
283
 
 
284
    for(i = 0; i < length; i++)  {
 
285
        current = current->trans[(unsigned char) buffer[i] & 0xff];
 
286
 
 
287
        if(current->islast) {
 
288
            position = i - AC_MIN_LENGTH + 1;
 
289
 
 
290
            pt = current->list;
 
291
            while(pt) {
 
292
                if(cli_findpos(buffer, position, length, pt)) {
 
293
                    if((pt->offset || pt->target) && (!pt->sigid || pt->partno == 1)) {
 
294
                        if(ftype == CL_TYPE_UNKNOWN_TEXT)
 
295
                            t = type;
 
296
                        else
 
297
                            t = ftype;
 
298
 
 
299
                        if((fd == -1 && !t) || !cli_validatesig(pt->target, t, pt->offset, offset + position, fd, pt->virname)) {
 
300
                            pt = pt->next;
 
301
                            continue;
 
302
                        }
 
303
                    }
 
304
 
 
305
                    if(pt->sigid) { /* it's a partial signature */
 
306
                        if(partcnt[pt->sigid] + 1 == pt->partno) {
 
307
                            dist = 1;
 
308
                            if(pt->maxdist)
 
309
                                if(offset + i - partoff[pt->sigid] > pt->maxdist)
 
310
                                    dist = 0;
 
311
 
 
312
                            if(dist && pt->mindist)
 
313
                                if(offset + i - partoff[pt->sigid] < pt->mindist)
 
314
                                    dist = 0;
 
315
 
 
316
                            if(dist) {
 
317
                                partoff[pt->sigid] = offset + i + pt->length;
 
318
 
 
319
                                if(++partcnt[pt->sigid] == pt->parts) { /* the last one */
 
320
                                    if(pt->type) {
 
321
                                        if(otfrec) {
 
322
                                            if(pt->type > type) {
 
323
                                                cli_dbgmsg("Matched signature for file type: %s\n", pt->virname);
 
324
                                                type = pt->type;
 
325
                                            }
 
326
                                        }
 
327
                                    } else {
 
328
                                        if(virname)
 
329
                                            *virname = pt->virname;
 
330
 
 
331
                                        return CL_VIRUS;
 
332
                                    }
 
333
                                }
 
334
                            }
 
335
                        }
 
336
 
 
337
                    } else { /* old type signature */
 
338
                        if(pt->type) {
 
339
                            if(otfrec) {
 
340
                                if(pt->type > type) {
 
341
                                    cli_dbgmsg("Matched signature for file type: %s\n", pt->virname);
 
342
 
 
343
                                    type = pt->type;
 
344
                                }
 
345
                            }
 
346
                        } else {
 
347
                            if(virname)
 
348
                                *virname = pt->virname;
 
349
 
 
350
                            return CL_VIRUS;
 
351
                        }
 
352
                    }
 
353
                }
 
354
 
 
355
                pt = pt->next;
 
356
            }
 
357
 
 
358
            current = current->fail;
 
359
        }
 
360
    }
 
361
 
 
362
    return otfrec ? type : CL_CLEAN;
 
363
}