afl-material: comparison videos/01-evilregexes.srt

equal deleted inserted replaced

-:a3418ee8c404
+:499405058cfd
 question mark, which says you
 38
 00:01:55,790 --> 00:01:59,105
 match either it is there
-or it ss not there.
+or it is not there.
 39
 00:01:59,105 --> 00:02:01,340
 You are also regular
 expressions which
 and z and 0 to 9 and so on.
 51
 00:02:33,635 --> 00:02:36,545
 Here you also have regular
-expression which can
+expressions which can
 52
 00:02:36,545 --> 00:02:40,070
 match something which
 isn't in this range.
 Okay, so these are the
 typical regular expressions.
 67
 00:03:19,925 --> 00:03:23,075
-And here's a particular one.
+And here's a particular one
 68
 00:03:23,075 --> 00:03:25,820
-Trying to match something
+trying to match something
 69
 00:03:25,820 --> 00:03:28,770
 which resembles
 an email address.
 match the regular expressions of
 a star star b.
 114
 00:05:42,935 --> 00:05:46,805
-And we measure time with longer
+And we measure the time with longer
-and longer strings of a.
+and longer strings of a's.
 115
 00:05:46,805 --> 00:05:48,770
 And so conveniently we can give
 00:06:07,640 --> 00:06:09,110
 did not match the string.
 123
 00:06:09,110 --> 00:06:11,255
-That's indicated by this none.
+That's indicated by this None.
 124
 00:06:11,255 --> 00:06:13,925
 Let's take ten a's.
 They are not 100
 percent accurate.
 130
 00:06:28,040 --> 00:06:31,490
-So 15 is also a let's take
+So 15 is also OK.
+Let's take 20.
 131
 00:06:31,490 --> 00:06:36,965
-28th notes already
+Hmmm this already takes
 double the time.
 132
 00:06:36,965 --> 00:06:42,440
-Twenty-five longer.
+Twenty-five. Then even longer.
 133
 00:06:42,440 --> 00:06:45,680
-Okay, that suddenly
+Okay, then suddenly
-from 02 seconds,
+from 0.2 seconds,
 134
 00:06:45,680 --> 00:06:48,960
-it takes almost four seconds.
+it now takes almost four seconds.
 135
 00:06:49,600 --> 00:06:54,890
-Six this
+Twenty-Six, this
 136
 00:06:54,890 --> 00:07:01,415
-takes six seconds
+takes six seconds...
-already Double, okay?
+already double.
 137
 00:07:01,415 --> 00:07:07,229
-Go to 28. That would be now.
+Let's go to 28. That would be
+...hmmm....hmmm
 138
 00:07:08,890 --> 00:07:11,840
 You see the string
 isn't very long,
 to find out that
 this string of 28
 144
 00:07:24,710 --> 00:07:26,570
-AES is actually not much
+a's is actually not matched
 145
 00:07:26,570 --> 00:07:28,490
-by that you see it's
+by that. You see it's
 still not finished.
 146
 00:07:28,490 --> 00:07:32,900
 I think it should take
 00:07:34,400 --> 00:07:36,530
 And if we would try
 149
 00:07:36,530 --> 00:07:40,805
-30 would be already
+30, we would be already here
-more than a minute.
+for more than a minute.
 150
 00:07:40,805 --> 00:07:43,940
-And if I could read
+And if I could use
-something like hundreds,
+something like 100,
 151
 00:07:43,940 --> 00:07:46,220
 you remember if a doubling in
 00:08:21,830 --> 00:08:23,930
 So there's not any difference
 166
 00:08:23,930 --> 00:08:26,150
-in the strings this work
+in the strings this regular
 expression matches.
 167
 00:08:26,150 --> 00:08:28,610
 We'll just start at the
 end of the string.
 169
 00:08:31,460 --> 00:08:35,285
 And we again, we just use
-repeated A's for that.
+repeated a's for that.
 170
 00:08:35,285 --> 00:08:38,195
 And similarly, we can
 call it on the command line
 and can do some timing.
 172
 00:08:41,930 --> 00:08:44,540
-So ten SBA, good.
+So ten a's is very good.
 173
 00:08:44,540 --> 00:08:46,340
 Here's the string.
 00:08:48,320 --> 00:08:50,525
 And it's pretty fast.
 176
 00:08:50,525 --> 00:08:54,725
-Friendly. Although pretty fast.
+Twenty...also pretty fast.
 177
 00:08:54,725 --> 00:08:59,120
-Five, again,
+Twenty-five... Again,
 178
 00:08:59,120 --> 00:09:06,650
-somehow is kind of
+somehow is a kind of
 threshold that is 25, 26.
 179
 00:09:06,650 --> 00:09:09,485
 Suddenly it takes much longer.
 00:09:14,360 --> 00:09:17,165
 So you'll see in now from 26 on,
 182
 00:09:17,165 --> 00:09:19,250
-the Times has always
+the times always
-doubling from
+double from
 183
 00:09:19,250 --> 00:09:21,860
 three seconds to seven seconds.
 27 and you see the
 string isn't very long.
 187
 00:09:30,230 --> 00:09:32,165
-Let's choose twenties or maize.
+It is just twenty-or-something a's.
 188
 00:09:32,165 --> 00:09:35,419
 Imagine you have to
 search a database
 189
 00:09:35,419 --> 00:09:38,720
-with kilobytes of data.
+with Gigabytes of data
 190
 00:09:38,720 --> 00:09:42,260
-This, these regular
+with these regular
-expressions that would years
+expressions that would
 191
 00:09:42,260 --> 00:09:48,150
 need years to go through with
 these regular expressions.
 00:10:01,045 --> 00:10:03,415
 You can see this again
 197
 00:10:03,415 --> 00:10:05,980
-is the reg expression
+is the regular expression
 and we just having
 198
 00:10:05,980 --> 00:10:08,320
 some scaffolding to generate
 199
 00:10:08,320 --> 00:10:11,905
-strings from five up till 28.
+strings from 5 up till 28.
 200
 00:10:11,905 --> 00:10:14,305
 And if we run that,
 So uphill 19, pretty fast,
 203
 00:10:19,900 --> 00:10:24,925
 but then starting from
-23, skidding pretty slow.
+23, it is getting pretty slow.
 204
 00:10:24,925 --> 00:10:27,445
 So the question is
 what's going on?
 205
 00:10:27,445 --> 00:10:29,230
-By the way, I'm not quoting here.
+By the way, I'm not gloating here.
 206
 00:10:29,230 --> 00:10:33,755
-Scala, using internally
+Scala uses internally
 the regular expression
 207
 00:10:33,755 --> 00:10:36,665
 matching engine from Java.
 We will see we can out-compete
 them by magnitudes.
 214
 00:10:55,490 --> 00:10:57,605
-So I think I can that.
+So I think I can
 215
 00:10:57,605 --> 00:10:59,165
-Now, just finish here.
+now, just finish this here.
 216
 00:10:59,165 --> 00:11:04,025
-You see the problem. Just
+You see the problem.
-for completeness sake.
+Just for completeness sake.
 217
 00:11:04,025 --> 00:11:07,010
 Here is a Ruby program.
 string should match.
 220
 00:11:12,935 --> 00:11:20,300
 And again it tries out
-strings between 130 here.
+strings between 1 and 30 here.
 221
 00:11:20,300 --> 00:11:23,450
 That's a program actually
 a former student produced.
 And you can see four a's
 223
 00:11:25,565 --> 00:11:29,780
 of links up till 20
-AES is pretty fast.
+a's is pretty fast.
 224
 00:11:29,780 --> 00:11:32,495
 But then starting at 26,
 00:11:49,610 --> 00:11:52,250
 as you will see later on.
 234
 00:11:52,250 --> 00:11:55,620
-Hey, I also just stop that here.
+I also just stop that here.
 235
 00:11:55,710 --> 00:12:00,985
-Okay, this slight collect
+Okay, this slide collects
-this information about times.
+the information about times.
 236
 00:12:00,985 --> 00:12:03,400
-On the right hand side will
+On the right-hand side will
 237
 00:12:03,400 --> 00:12:05,860
-be our regular expression mantra,
+be our regular expression matcher,
 238
 00:12:05,860 --> 00:12:08,290
 which we implement next week.
 On the left-hand side,
 are these times by
 240
 00:12:10,795 --> 00:12:14,260
-barriers than regular
+various other regular
 expression matching engines?
 241
 00:12:14,260 --> 00:12:17,809
 On the top is this
 regular expression.
 242
 00:12:19,080 --> 00:12:23,335
-Possible a n times a n times.
+Possible a n-times a n-times.
 243
 00:12:23,335 --> 00:12:26,890
-And on the lowest
+And on the lower
-is a star, star b.
+is (a*)* b.
 244
 00:12:26,890 --> 00:12:30,370
 And the x-axis show here
 the length of the
 string. How many a's.
 246
 00:12:35,335 --> 00:12:38,925
-And on the y axis is the time.
+And on the y-axis is the time
 247
 00:12:38,925 --> 00:12:41,660
-They need to decide whether
+they need to decide whether
 248
 00:12:41,660 --> 00:12:44,615
 the string is matched by
-the rate expression or not.
+the regular expression or not.
 249
 00:12:44,615 --> 00:12:46,415
 So you can see here, Python,
 250
 00:12:46,415 --> 00:12:47,945
-Java eight in JavaScript,
+Java 8 and JavaScript,
 251
 00:12:47,945 --> 00:12:52,250
 they max out approximately
-at between 2530.
+at between 25 and 30.
 252
 00:12:52,250 --> 00:12:53,900
-The kristin, it takes already
+Because then it takes already
 253
 00:12:53,900 --> 00:12:55,160
 a half a minute to
 And similarly, in
 the other example,
 256
 00:13:00,815 --> 00:13:03,830
-Python and derived Ruby max out
+Python and Ruby max out
 257
 00:13:03,830 --> 00:13:07,220
 at a similar kind of
 length of the strings.
 Because then they use also
 half a minute to decide
 259
 00:13:10,400 --> 00:13:13,940
-whether this rec expression
+whether this regular expression
 actually matches the string.
 260
 00:13:13,940 --> 00:13:16,790
 Contrast that with
-the reg expression
 261
 00:13:16,790 --> 00:13:19,235
-which we are regular
+the regular expression matcher
-expression mantra,
 262
 00:13:19,235 --> 00:13:21,470
 which we're going to implement.
 Actually, there will be
 two versions of that.
 266
 00:13:32,285 --> 00:13:34,850
-First version may be
+The first version will be
 also relatively slow.
 267
 00:13:34,850 --> 00:13:36,410
 But the second version,
 And in the second example,
 271
 00:13:42,380 --> 00:13:45,740
 you have to be careful
-about the x axis because
+about the x-axis because
 272
 00:13:45,740 --> 00:13:49,385
 that means four times
 ten to the power six.
 273
 00:13:49,385 --> 00:13:51,695
-It's actually 4 million A's.
+It's actually 4 million a's.
 274
 00:13:51,695 --> 00:13:55,100
 So our regular
-expression match or need
+expression matcher needs
 275
 00:13:55,100 --> 00:13:57,635
 less than ten seconds to
 276
 00:13:57,635 --> 00:14:00,725
 match a string of length
-of 4 million A's.
+of 4 million a's.
 277
 00:14:00,725 --> 00:14:04,430
-Contrast that Python, Java eight,
+Contrast that Python, Java 8,
 278
 00:14:04,430 --> 00:14:06,770
 and JavaScript need half a minute
 279
 00:14:06,770 --> 00:14:09,905
 already for a string
-of length just 30,
+of length just 30.
 280
 00:14:09,905 --> 00:14:12,365
-unless you're very
+I was very careful with Java 8.
-careful with Java eight.
 281
 00:14:12,365 --> 00:14:15,725
-Yes, Java nine and above,
+Yes, Java 9 and above,
 282
 00:14:15,725 --> 00:14:17,180
 they already have
 but still we will be running
 circles around them.
 285
 00:14:22,805 --> 00:14:27,050
-It's this data. I
+with this data.
-call this slide.
+I call this slide:
 286
 00:14:27,050 --> 00:14:29,675
 Why bother with
 regular expressions?
 But you can probably
 see these are
 288
 00:14:33,515 --> 00:14:34,910
-at least more times by
+abysmal times by
 289
 00:14:34,910 --> 00:14:38,015
 the existing regular
 expression matching engines.
 do substantially better.
 292
 00:14:42,695 --> 00:14:47,495
 And if you don't believe
-in D times, I gave here,
+in the times, I gave here,
 293
 00:14:47,495 --> 00:14:50,090
 please feel free to
 play on your own
 294
 00:14:50,090 --> 00:14:52,865
 with the examples
-I uploaded, Keats.
+I uploaded on KEATS.
 295
 00:14:52,865 --> 00:14:55,235
 These are exactly the programs
 296
 00:14:55,235 --> 00:14:57,470
-are used here in the examples.
+I used here in the examples.
 297
 00:14:57,470 --> 00:14:59,255
 So feel free.
 You might however now think, hmm.
 299
 00:15:01,970 --> 00:15:05,449
 These are two very
-well chosen examples.
+well chosen examples,
 300
 00:15:05,449 --> 00:15:07,145
-And I admit that's true.
+and I admit that's true,
 301
 00:15:07,145 --> 00:15:09,410
-And such problem there never
+and such problems never
 302
 00:15:09,410 --> 00:15:12,540
-causing any problems
+cause any problems
 in real life.
 303
 00:15:13,300 --> 00:15:15,980
 Regular expressions are used very
 00:15:19,415 --> 00:15:21,410
 So here's my first example from
 306
 00:15:21,410 --> 00:15:23,885
-a company called cloudflare.
+a company called Cloudflare.
 307
 00:15:23,885 --> 00:15:27,560
 This is a huge hosting company
 308
 00:15:27,560 --> 00:15:30,935
-which host very
+which hosts very
 well-known web pages.
 309
 00:15:30,935 --> 00:15:34,970
 And they really try hard
 And they manage
 that for six years.
 311
 00:15:37,340 --> 00:15:39,320
-But then a Rekha expression,
+But then a regular expression,
 312
 00:15:39,320 --> 00:15:41,180
-actually this one caused
+actually this one, caused
 a problem and you
 313
 00:15:41,180 --> 00:15:43,265
 can see they're also
-like two stars.
+two stars
 314
 00:15:43,265 --> 00:15:44,630
-They are at the end.
+at the end.
 315
 00:15:44,630 --> 00:15:46,955
 And because of that string needed
 where Stack Exchange,
 I guess you know
 323
 00:16:04,040 --> 00:16:06,650
-this webpage had
+this webpage, had
-also an outage from,
+also an outage for
 324
 00:16:06,650 --> 00:16:08,390
 I think at least an hour.
 325
 00:16:08,390 --> 00:16:13,070
-Because a regular expression
+Because a regular expression,
-then needed to format posts,
+needed to format posts,
 326
 00:16:13,070 --> 00:16:15,575
 needed too much time to
 should be accepted or not.
 328
 00:16:19,010 --> 00:16:23,390
 And again, there was a
-semi kind of problem.
+similar kind of problem.
 329
 00:16:23,390 --> 00:16:24,950
 And you can read
 the stories behind
 this the first time,
 332
 00:16:31,730 --> 00:16:34,175
 what surprised me is
-that theoretician
+that theoreticians,
 333
 00:16:34,175 --> 00:16:37,520
 who sometimes dedicate their
-life to regular expression.
+life to regular expressions
 334
 00:16:37,520 --> 00:16:39,440
-And no really a lot about
+and know really a lot about
 335
 00:16:39,440 --> 00:16:41,690
-them didn't know
+them, didn't know
 anything about this.
 336
 00:16:41,690 --> 00:16:43,610
 But engineers, they
 already created
 337
 00:16:43,610 --> 00:16:46,160
-a name for that
+a name for that:
-regular expression,
+Regular Expression
 338
 00:16:46,160 --> 00:16:47,975
-denial of service attack.
+Denial of Service Attack.
 339
 00:16:47,975 --> 00:16:49,745
 Because what you can,
 what can happen now is that
 341
 00:16:51,230 --> 00:16:54,920
 attackers look for
-certain strings.
+certain strings
 342
 00:16:54,920 --> 00:16:56,780
-You make your regular expression
+that make your regular expression
 343
 00:16:56,780 --> 00:16:59,105
 matching engine topple over.
 344
 00:16:59,105 --> 00:17:01,370
-And these kind of expressions,
+And these kind of
 345
 00:17:01,370 --> 00:17:04,160
-regular expressions called
+regular expressions are called
-Eve of reg expression.
+Evil Regular Expressions.
 346
 00:17:04,160 --> 00:17:06,350
 And actually there are
 quite a number of them.
 And you can easily have in
 351
 00:17:15,620 --> 00:17:18,560
 your program one of
-these reg expression.
+these regular expressions.
 352
 00:17:18,560 --> 00:17:21,830
 And then you have the
 problem that if you do have
 somebody finds the
 corresponding string,
 355
 00:17:25,640 --> 00:17:29,945
-which make the records
+which make the regular
 matching engine topple over,
 356
 00:17:29,945 --> 00:17:31,820
 then you have a problem
 357
 00:17:31,820 --> 00:17:34,295
 because your webpage is
-probably not variable.
+probably not available.
 358
 00:17:34,295 --> 00:17:36,140
-This is also sometimes called
+This phenomenon is also sometimes
 359
 00:17:36,140 --> 00:17:39,350
-this phenomenon,
+called
 catastrophic backtracking.
 360
 00:17:39,350 --> 00:17:43,595
 In lecture three, we will
 is such a problem in
 362
 00:17:46,910 --> 00:17:50,795
 real life is actually
-not to do with Lexus.
+not to do with lexers.
 363
 00:17:50,795 --> 00:17:53,180
 Yes, regular
 expressions are used as
 00:17:53,180 --> 00:17:55,040
 the basic tool for implementing
 365
 00:17:55,040 --> 00:17:57,185
-like source bad reg expressions,
+lexers. But regular expressions,
 366
 00:17:57,185 --> 00:18:00,065
 of course, used in
 a much wider area.
 And they especially used for
 network intrusion detection.
 368
 00:18:03,770 --> 00:18:06,590
-Remember, you having to
+Remember, say you're having to
 369
 00:18:06,590 --> 00:18:10,130
 administer a big network
 and you only want to let
 370
 00:18:10,130 --> 00:18:13,640
-in packets which you think are K
+in packets which you think are OK
 371
 00:18:13,640 --> 00:18:14,930
 and you want to keep out
 the problem is that our
 hardware is already
 381
 00:18:39,080 --> 00:18:43,190
-so fast that the reg expressions
+so fast that the regular
+expressions
 382
 00:18:43,190 --> 00:18:45,169
 really become a bottleneck.
 00:18:45,169 --> 00:18:47,060
 Because what do you do if now is
 384
 00:18:47,060 --> 00:18:49,880
-suddenly a reg expression
+suddenly a regular expression
-takes too much time
+takes too much time?
 385
 00:18:49,880 --> 00:18:52,670
-to just stop the matching
+Do you just stop the matching
 386
 00:18:52,670 --> 00:18:55,100
 and let the package
 in regardless?
 by this engineer.
 392
 00:19:09,965 --> 00:19:13,820
 And it's always say that
-Germans don't have any Yammer.
+Germans don't have any humor.
 393
 00:19:13,820 --> 00:19:16,985
 But I found that
 video quite funny.
 different opinion,
 395
 00:19:19,145 --> 00:19:21,095
 but feel free to
-have a look which
+have a look.
 396
 00:19:21,095 --> 00:19:23,705
-explains exactly that problem.
+It explains exactly that problem.
 397
 00:19:23,705 --> 00:19:25,610
 So in the next video,

changeset 837	499405058cfd
parent 765	b294cfbb5c01