/ 
Perl6-Pugs-6.2.0
/ Junc.pod
Security Advisories (11)
CVE-2006-7230 (2007-11-15)

Perl-Compatible Regular Expression (PCRE) library before 7.0 does not properly calculate the amount of memory needed for a compiled regular expression pattern when the (1) -x or (2) -i UTF-8 options change within the pattern, which allows context-dependent attackers to cause a denial of service (PCRE or glibc crash) via crafted regular expressions.

CVE-2007-1660 (2007-11-07)

Perl-Compatible Regular Expression (PCRE) library before 7.0 does not properly calculate sizes for unspecified "multiple forms of character class", which triggers a buffer overflow that allows context-dependent attackers to cause a denial of service (crash) and possibly execute arbitrary code.

CVE-2007-1659 (2007-11-07)

Perl-Compatible Regular Expression (PCRE) library before 7.3 allows context-dependent attackers to cause a denial of service (crash) and possibly execute arbitrary code via regex patterns containing unmatched "\Q\E" sequences with orphan "\E" codes.

CVE-2007-1661 (2007-11-07)

Perl-Compatible Regular Expression (PCRE) library before 7.3 backtracks too far when matching certain input bytes against some regex patterns in non-UTF-8 mode, which allows context-dependent attackers to obtain sensitive information or cause a denial of service (crash), as demonstrated by the "\X?\d" and "\P{L}?\d" patterns.

CVE-2007-1662 (2007-11-07)

Perl-Compatible Regular Expression (PCRE) library before 7.3 reads past the end of the string when searching for unmatched brackets and parentheses, which allows context-dependent attackers to cause a denial of service (crash), possibly involving forward references.

CVE-2007-4766 (2007-11-07)

Multiple integer overflows in Perl-Compatible Regular Expression (PCRE) library before 7.3 allow context-dependent attackers to cause a denial of service (crash) or execute arbitrary code via unspecified escape (backslash) sequences.

CVE-2007-4767 (2007-11-07)

Perl-Compatible Regular Expression (PCRE) library before 7.3 does not properly compute the length of (1) a \p sequence, (2) a \P sequence, or (3) a \P{x} sequence, which allows context-dependent attackers to cause a denial of service (infinite loop or crash) or execute arbitrary code.

CVE-2007-4768 (2007-11-07)

Heap-based buffer overflow in Perl-Compatible Regular Expression (PCRE) library before 7.3 allows context-dependent attackers to execute arbitrary code via a singleton Unicode sequence in a character class in a regex pattern, which is incorrectly optimized.

CVE-2015-2325 (2020-01-14)

The compile_branch function in PCRE before 8.37 allows context-dependent attackers to compile incorrect code, cause a denial of service (out-of-bounds heap read and crash), or possibly have other unspecified impact via a regular expression with a group containing a forward reference repeated a large number of times within a repeated outer group that has a zero minimum quantifier.

CVE-2015-2326 (2020-01-14)

The pcre_compile2 function in PCRE before 8.37 allows context-dependent attackers to compile incorrect code and cause a denial of service (out-of-bounds read) via regular expression with a group containing both a forward referencing subroutine call and a recursive back reference, as demonstrated by "((?+1)(\1))/".

CVE-2015-8382 (2015-12-02)

The match function in pcre_exec.c in PCRE before 8.37 mishandles the /(?:((abcd))|(((?:(?:(?:(?:abc|(?:abcdef))))b)abcdefghi)abc)|((*ACCEPT)))/ pattern and related patterns involving (*ACCEPT), which allows remote attackers to obtain sensitive information from process memory or cause a denial of service (partially initialized memory and application crash) via a crafted regular expression, as demonstrated by a JavaScript RegExp object encountered by Konqueror, aka ZDI-CAN-2547.

NAME

Junc.pod - explanation of how Junc.hs works

OVERVIEW

I am a fledgling Haskell programmer having just finished reading YAHT. For some reason, I was attracted to understanding Junc.hs and so will document its workings.

Junc.hs is the main code for implementing Perl6 Junctions:

http://dev.perl.org/perl6/synopsis/S09.html

HOW THE MODULE WORKS

First we load in the Internals and the abstract syntax tree, AST.

The first thing to understand is how opJunc works. It's just the first function in the file, but it is important, so let's get down to business.

opJunc

The type signature of this function is

opJunc :: JuncType -> [Val] -> Val

which means it takes a JuncType and a list of type Val and returns an element of type Val. More properly this function returns an element of type VJunc, but you cannot specify that a function returns a subtype only a type.

Here is it's definition. Let's understand it:

opJunc :: JuncType -> [Val] -> Val
opJunc t vals = VJunc $ Junc t emptySet (joined `union` mkSet vs)
   where
   joined = unionManySets $ map (\(VJunc s) -> juncSet s) js
   (js, vs) = partition sameType vals
   sameType (VJunc (Junc t' _ _))  = t == t'
   sameType _                      = False

sameType and partition

js and vs are defined by a call to partition, which takes a list of elements and returns a list in which the first list is those elements which satisfied a predicate and the second list is those which failed. So, js turns out to be all elements which are the same as the type we passed in and vs are the ones which are not the same type. How does sameType work? The call to sameType is using pattern matching. VJunc, if you look in AST.hs, is part of some punnery being used in the Val enumerated set type. VJunc is both a data constructor and it receives a parameter of type VJunc which is defined further down. Pattern matching the first element of a value of type VJunc extracts the type of the VJunct. If the two types are equal, then we have the same type.

So now we understand 75% of the where clauses for opJunc. Now for 100% closure on where let's understand joined :

joined

joined = unionManySets $ map (\(VJunc s) -> juncSet s) js

Well, we know that js is the list of values that are the same type of as the passed-in type. Now, this function:

(\(VJunc s) -> juncSet s)

might look a little funny but it's simple. We are pulling the juncSet slot from a value (namely s) whose type is VJunct. In Perl5 you might do $s->{juncSet} for the same effect.

So, all the map is doing is extracting the juncSet fields from a list of values of type VJunc. Then this list is passed to unionManySets:

http://www.haskell.org/ghc/docs/5.04.3/html/base/Data.Set.html#unionManySets

which takes a list of Sets and turns them into a single set.

Now that we know what each of the where clauses does for the main clause, let's understand the main clause:

opJunc t vals = VJunc $ Junc t emptySet (joined `union` mkSet vs)

in the context of a real call to it:

opJuncAll = opJunc JAll

isTotalJunc, isPartialJunc (in the context of ApplyArg)

Both isTotalJunc and isPartialJunc operate on a single piece of data of type ApplyArg. The ApplyArg value slot must be of type VJunc or either function will return False.

isTotalJunc tests to see if the VJunc value slot is of type JAll or JNone. Note that unlike most tests which return True if their test passes, this function (and isPartialJunc) return the negation of the argCollapsed slot.

isPartialJunc tests to see if the VJunc value slot is of type JOne or JAny. It also returns the negation of the argCollapsed slot if this test passes and False otherwise.

TODO

errata

20:58] <autrijus> it will take some used to at first [20:58] <autrijus> but the context will make it clear [20:58] <autrijus> cool with it? [20:59] <autrijus> juncSet is used for all junctions [20:59] <metaperl> yes [20:59] <autrijus> juncDup is only used for none() [20:59] <autrijus> the reason is that none() cannot be represent as one set [20:59] <autrijus> must use two sets.

argsCollapsed

AUTHOR

metaperl with help from Cale, Igloo