I implemented the pseudocode given in the paper using Python. The git repository can be found here: https://github.com/josch/cycles_tarjan
Enumeration of the elementary circuits of a directed graph R. Tarjan, SIAM Journal on Computing, 2 (1973), pp. 211-216 http://dx.doi.org/10.1137/0202017
In the worst case, Tarjan's algorithm has a time complexity of O(n e(c+1)) whereas Johnson's algorithm supposedly manages to stay in O((n+e)(c+1)) where n is the number of vertices, e is the number of edges and c is the number of cycles in the graph. I found two implementations of Johnson's algorithm. One was done by Frank Meyer and can be downloaded as a zip archive. The other was done by Pietro Abate and the code can be found in a blog entry which also points to a git repository. The implementation by Frank Meyer seemed to work flawlessly. I only had to add code so that a graph could be given via commandline. The git repository of my additions can be found here: https://github.com/josch/cycles_johnson_meyer Pietro Abate implemented an iterative and a functional version of Johnson's algorithm. It turned out that both yielded incorrect results as some cycles were missing from the output. A fixed version can be found in this git repository: https://github.com/josch/cycles_johnson_abate
Finding all the elementary circuits of a directed graph. D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975. http://dx.doi.org/10.1137/0204007
In contrast to Johnson's algorithm, the algorithm by K. A. Hawick and H. A. James is able to handle graphs containing edges that start and end at the same vertex as well as multiple edges connecting the same two vertices. I do not need this functionality but add the code as additional verification. The paper posts extensive code snippets written in the D programming language. A full, working version with all pieces connected together can be found here: https://github.com/josch/cycles_hawick_james The algorithm was verified using example output given in the paper. The project README states how to reproduce it.
Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs. Hawick and H.A. James, In Proceedings of FCS. 2008, 14-20 www.massey.ac.nz/~kahawick/cstn/013/cstn-013.pdf
To generate the list of elementary circuits using Tarjan's algorithm for the graph above, use:
digraph G 0; 1; 2; 0 -> 1; 0 -> 2; 1 -> 0; 2 -> 0; 2 -> 1;
The commandline arguments are the exact same for the other three methods and yield the same result in the same order. If the DOT graph is in a format as simple as above, the following sed construct can be used to generate the commandline argument that represents the graph:
$ python cycles.py 3 0,1 0,2 1,0 2,0 2,1 0 1 0 2 0 2 1
$ echo sed -n -e '/^\s*[0-9]\+;$/p' graph.dot wc -l sed -n -e 's/^\s*\([0-9]\) -> \([0-9]\);$/\1,\2/p' graph.dot
A testrun is done via calling:
$ git clone git://github.com/josch/cycle_test.git $ cd cycle_test $ git submodule update --init
The argument to the shell script is an integer denoting the maximum number
$ ./test.sh 11
Nof vertices for which graphs will be generated. The script will compile the Ocaml, Java and D sourcecode of the submodules as well as an ocaml script called
rand_graph.mlwhich generates random graphs from
v = 1..Nvertices where
Nis given as a commandline argument. For each number of vertices
e = 1..Mnumber of edges are chosen where
Mis maximum number of edges given the number of vertices. For every combination of number of vertices
vand number of edges
e, a graph is randomly generated using
Pack.Digraph.Rand.graphfrom the ocamlgraph library. Each of those generated graphs is checked for cycles and written to a file
graph-v-e.dotif the graph contains a cycle.
test.shthen loops over all generated dot files. It uses the above sed expression to convert each dot file to a commandline argument for each of the algorithms. The outputs of each algorithm are then compared with each other and only if they do not differ, does the loop continue. Otherwise the script returns with an exit code. The tested algorithms are the Python implementation of Tarjan's algorithm, the iterative and functional Ocaml implementation as well as the Java implementation of Johnson's algorithm and the D implementation of the algorithm by Hawick and James.
|Johnson, Abate, Ocaml, iterative||137|
|Johnson, Abate, Ocaml, functional||139|
|Johnson, Meyer, Java||357|
arch/x86/mm/dump_pagetables.cto be a loadable module so I could look at
/sys/kernel/debug/kernel_page_tableswithout needing to rebuild my kernel with CONFIG_X86_PTDUMP. Comparing Lucid (2.6.32), Maverick (2.6.35), and Natty (2.6.38), it s clear to see the effects of the RO/NX improvements, especially in the Modules section which has no NX markings at all before 2.6.38:
lucid-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables grep NX wc -l 0 maverick-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables grep NX wc -l 0 natty-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables grep NX wc -l 762.6.38 s memory region is much more granular, since each module has been chopped up for the various segment permissions:
lucid-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables wc -l 53 maverick-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables wc -l 67 natty-amd64# awk '/Modules/,/End Modules/' /sys/kernel/debug/kernel_page_tables wc -l 155For example, here s the large sunrpc module. RW is read-write, ro is read-only, x is executable, and NX is non-executable:
maverick-amd64# awk '/^'$(awk '/^sunrpc/ print $NF ' /proc/modules)'/','!/GLB/' /sys/kernel/debug/kernel_page_tables 0xffffffffa005d000-0xffffffffa0096000 228K RW GLB x pte 0xffffffffa0096000-0xffffffffa0098000 8K pte natty-amd64# awk '/^'$(awk '/^sunrpc/ print $NF ' /proc/modules)'/','!/GLB/' /sys/kernel/debug/kernel_page_tables 0xffffffffa005d000-0xffffffffa007a000 116K ro GLB x pte 0xffffffffa007a000-0xffffffffa0083000 36K ro GLB NX pte 0xffffffffa0083000-0xffffffffa0097000 80K RW GLB NX pte 0xffffffffa0097000-0xffffffffa0099000 8K pteThe latter looks a whole lot more like a proper ELF (text segment is read-only and executable, rodata segment is read-only and non-executable, and data segment is read-write and non-executable). Just another reason to make sure you re using your CPU s NX bit (via 64bit or 32bit-PAE kernels)! (And no, PAE is not slower in any meaningful way.)
pkg-core => pkg-A, pkg-D
# circle 1: A, B, C
pkg-A => pkg-B
pkg-B => pkg-C
pkg-C => pkg-A
# circle 2: D, E, FIn this case, our current tool will be able to tell that all packages (possibly except root I did not check) are in a circular relationship. However, we can find better results by pretending we are trying to find Strongly Connected Components (actually that is exactly what we are trying to do here). So today, I implemented Tarjan s algorithm in Perl to solve this particular issue and committed it to my Lintian branch. If this branch is merged into the Lintian master branch, we can close #316283.
pkg-D => pkg-E
pkg-E => pkg-F
pkg-F => pkg-D
Recently there has been some major developments in DebConf11 organization. In short, I will list some of the most important.
Official DC11 website has finally been completed and now contains a great deal of information for those interested in attending this years conference. Some of the most notable changes include:
Frontpage now contains a small menu with links to most important parts of website, like About, Registration, Contact Sidebar menu is now divided in 3 categories:
Site is now available on Bosnian language for native speaking attendees, should they have problems with English version. Every page is available on both languages, which can be changed by clicking on ba/en flag in upper left corner, or DC11: Bosnian Version.
As you may have noticed, the official page received a small face lift. New header with the Government building, a small token of appreciation for all the help the Government is providing; as well as some minor changes in CSS and color scheme. While talking about design, we d like to thank Leandro G mez for his help with the header.
As agreed on the meeting, which took place on 22. of February, [Meeting logs], following sponsorship levels will be used for this years conference:
Main reason for lowering amounts is due to last years results of high increase in the same. As for the benefits of these levels, the only thing changed is t-shirts / bags places; we believe t-shirts are much more noticeable than bags, and have therefore been promoted to Silver, while bags have been downgraded to Bronze. For a full list of requirements and benefits, please visit: DC11: Sponsorship Sponsorship Brochure
Sponsorship brochures have finally been completed and are available for a public distribution. The brochures are available in 3 qualities: low, high and original. Low and high quality brochures, ~6Mb and ~8Mb respectively, are for normal distribution to our sponsors, while original quality, at around 240Mb, is intended for maximum quality printing. Just as with the website, each quality is available in both Bosnian and English. Current version of the brochure is 1.1 and is most likely the final one. These brochures are available at Documentation page: DC11: Documentation >> Documents made by Local Team Or download them directly:
Also, I d like to thank Mirosal Remetic for making a great template and Pablo Duboue for some very valuable suggestions regarding the structure of the brochure.
Many questions have been raised regarding Bosnian visa regime. We got in contact with the embassy and they clarified who can enter our country with(out) Visa. The list can be found on DC11 Wiki: Visa regime. It also states, which countries have a privilidge of ID-only entrance. If your country is not listed, that means you will need visa. If you want to know what exactly you need to get one, please visit the this official Government page and chose your country from a drop-down menu. As for the visa itself, as well as the list of Customs Rules, please read DC11: Visa.
Also, thanks to Darjan Prtic for getting the list from the Government officials.
If you think, that is it for now, you are dead wrong. At this very moment following is being organized and developed:
Well, these are pretty much the highlights of some recent and some future developments of DebConf11 organizational team. Mind you, there s a lot more going on, but I tried to give a small summary from the inside. Should you be interested in attending, helping out, sponsoring or just have some questions, feel free to ask them on our mailing list at: firstname.lastname@example.org. I should inform you that this is a public mailing list and its archives are available for a broader public. If you do not wish for your mail to be made public, please direct any enquiry directly to me trough the Contact Form or any other member of Core Local Team, Adnan Hodzic or Velimir Iveljic.
We get this:
$ ./vulnerable-setuid-program $OVERFLOW_AND_SHELLCODE
uid=0(root) gid=0(root) groups=0(root)
Though, as always, please just use 64bit instead. :) Update: gave credit to PaX, thanks for the corrections!
$ ./vulnerable-setuid-program $OVERFLOW_AND_SHELLCODE
Segmentation fault (core dumped)
$ dmesg tail -n1
[170131.763976] vulnerable-set: general protection ip:80489c5 sp:bfa3e330 error:0 in vulnerable-setuid-program[8048000+1000]
libdg = package.loadlib("./libdebgraph.so", "luaopen_libdebgraph") libdg() LoadPackages('cache') -- 'g' is the main graph of unstable binary-arm packages cycles = FindCycles(g) print("Found " .. #fc .. " cycles") for comp_key,comp in pairs(cycles) do comp_nodes = "" for node_key,node in pairs(comp) do prop = GetProperty(node, "Package") comp_nodes = comp_nodes .. prop .. " " end print("* " .. comp_nodes) endThe above Lua script produces the following result:
reading cache/unstable/main/binary-arm/Packages Found 61 cycles * debconf-english debconf-i18n debconf * perl-modules perl * cdebconf fontconfig-config fontconfig gsfonts-x11 libcairo2 libfontconfig1 libgtk2.0-0 libpango1.0-0 libpango1.0-common libxft2 ucf x11-utils xutils [...]These are the package names in the strongly connected components, shown in alphabetical order. There is still a lot of work to do before the Lua binding will achieve feature parity with the core library, but we have now laid the foundation (and a brick or two).