recovering tokens from (f)lex generated code

While doing some reverse engineering of ptxas I discovered that their lexer was generated by lex in fast mode (lex -f). Knowing that nvidia trying to hide from us as much as possible it would be good to extract what tokens their lexer able to consume. Surprisingly I was unable to find in google solution for this simple task of tokens recovery. And even worse - seems that nobody understand how 40 year code in lex DFA works. So as usually I had do it by myself

 

Code

Lets check how generated code looks like:

struct yy_trans_info
        {
        flex_int32_t yy_verify;
        flex_int32_t yy_nxt;
        };
static const struct yy_trans_info *yy_start_state_list[3] =
    {
    &yy_transition[1],
    &yy_transition[3],
    &yy_transition[24],
    } ; 

if ( ! (yy_start) )
   (yy_start) = 1; /* first start state */

while(1) {


  yy_current_state = yy_start_state_list[(yy_start)];
yy_match:
  {
     const struct yy_trans_info *yy_trans_info;
     YY_CHAR yy_c;

     for ( yy_c = YY_SC_TO_UI(*yy_cp);
             (yy_trans_info = &yy_current_state[yy_c])->yy_verify == yy_c;
             yy_c = YY_SC_TO_UI(*++yy_cp) )
      {
         yy_current_state += yy_trans_info->yy_nxt;
         if ( yy_current_state[-1].yy_nxt )
         {
            (yy_last_accepting_state) = yy_current_state;
            (yy_last_accepting_cpos) = yy_cp;
          }
      }
yy_find_action:
      yy_act = yy_current_state[-1].yy_nxt;
do_action:
      switch ( yy_act )
       { /* beginning of action switch */
           case 0: /* must back up */
           /* undo the effects of YY_DO_BEFORE_ACTION */
           *yy_cp = (yy_hold_char);
           yy_cp = (yy_last_accepting_cpos) + 1;
           yy_current_state = (yy_last_accepting_state);
           goto yy_find_action;
 

sass instructions: LUT operations

I was asked yesterday why I didn't transformed sample from my previous record


iadd r8, r2, r8 ; r8 = r2 + r8
iadd r8, r8, r8 ; r8 = r8 + r8
iadd r8, r8, ur4 ; r8 = r8 + ur4

to more simple

imad r8, r8, 2, ur4 ; r8 = r8 * 2 + ur4

While this is technically correct the problem here - ISA is non-orthogonal. You can use my ina to check available forms of IMAD for universal registers - and suddenly we will discover that it has only 2 forms

1. @Pg IMAD E:wide E:fmt E:Rd E:Pu E:Ra E:reuse_src_a E:Rb E:reuse_src_b -E:URc
2. @Pg IMAD E:wide E:fmt E:Rd E:Pu E:Ra E:reuse_src_a E:URb -E:Rc E:reuse_src_c
   

And no forms with imm value for Ra/Rb. So you can generate only something like:

imad r8, r8, rXX, ur4

And for UIMAD with imm values we have forms with universal registers only:

1. @UPg UIMAD E:wide E:fmt E:X E:URd E:UPu E:URa ,Sb ~E:URc !E:UPp
2. @UPg UIMAD E:wide E:fmt E:URd E:UPu E:URa ,Sb -E:URc
3. etc
   

But all this is just kids games compared to LUT operations. In short - you can have 255 combinations of logical operations over 3 operands driven by index. nvdisasm shows them like:

LOP3.LUT R0, R3, R0, RZ, 0x30, !PT 

Very informative, yeah. So I employed sympy to generate table of simplified expressions - however I am too old and lazy to write python scripts. So pretty obvious solution:

• make perl script to enumerate all possible combinations and generate python script
• which in turn generates string table
• and then sed add quotes and commas
  

And now my disasm shows much clearer output:
LOP3.LUT PT,R0,R3,R0,RZ, 0x30,!PT &req={5}; LUT 30: a & ~b
So here a = R3, b = R0 and result R0 = R3 & ~R0

Filling Trominos

IMHO this is very hard task - only 104 accepted solutions. My solution is here

Google gives lots of links for trominos but they all for totally different task from Euler Project - in our case we have only L-shapes. So lets think about possible algorithm

It`s pretty obvious that we can make 2 x 3 or 3 x 2 rectangles with couple of L-trominos. So naive solution is just to check if one size is divisible by 2 and other by 3

However with pen and paper you can quickly realize that you can for example fill rectangle 5 x 6:

aabaab
abbabb
ccddee
dcdced
ddccdd


Algo can look like (see function check2x3)

• if one side of rectangle is divisible by 6 then another minus 2 should be divisible by 3
• if one side of rectangle is divisible by 6 then another minus 3 should be divisible by 2

Submit our solution and from failed tests suddenly discovering that you also can have rectangle 9 x 5. Some details how this happens

So we can have maximal 3 groups of different shapes:

• 9 x 5 rectangle (or even several if sides multiples of 5 & 9) - in my solution it stored in field has_95
  
• 1 or 2 groups of 2 x 3 rectangles below 9 x 5 shape. 1 for case when you can fill this area with shapes 2 x 3 of the same orientation and 2 if you must mix vertical and horizontal rectangles - field trom
  
• the same 1 or 2 groups on right of 9 x 5 shape - field right

Now the only remained problem is coloring

Rectangle 9 x 5 has 5 different colors but it is possible to arrange trominos in such way that on borders it will have only 4 colors and 5th is inside. For groups of 2 x 3 rectangles you need 4 colors if group size is 1 and yet 4 if size is 2. In worst case number of colors is 4 for 9 x 5 + 2 * 2 * 4 = 20 - so we can fit in A-Z

my solutions for couple CSES tasks

CSES has two very similar by description tasks but with completely different solutions: "Critical Cities" (218 accepted solutions at time when I writing this) and "Visiting Cities" (381 accepted solutions)

Critical Cities

We are given an directed unweighted graph and seems that we need to find it`s dominators for example using Lengauer-Tarjan algo (with complexity O((V+E)log(V+E))

Then we could check each vertex in this dominators tree to see if it leads to target node, so overall complexity is O(V * (V+E)log(V+E))

 

This looks not very impressive IMHO. Lets try something completely different (c) Monty Python's Flying Circus. For example we could run wave (also known as Lee algorithm) from source to target and get some path with complexity O(V+E). Note that in worst case this path can contain all vertices. Lets mark all vertices in this path

Next we could continue to run waves but at this time ignoring edges from marked nodes and see what marked vertices are still reachable. For example on some step k we run wave from Vs and reached vertices Vi and Vj. We can conclude that all vertices in early found path between Vs and Vj are NOT critical cities. So we can repeat next step starting with Vj

This process can be repeated in worst case V times so overall complexity is O(V*(V+E))

 

My solution is here

 

Visiting Cities

At this time we are given an directed weighted graph and seems that simplest solution is to find all K-th shortest paths (for example with Yen algo) and make union of their vertices. Because I'm very lazy I decided to reuse some ready and presumably well-tested implementation of this algo. You can read about fabulous results here
 

After that I plunged into long thoughts until I decided to count how many paths of minimal length go through each vertex - actually we could run Dijkstra in both directions: from source to target and from target to source, counting number of paths with minimal length. And then we could select from this path vertices where product of direct counts with reverse equal to direct count on target (or reverse count on source) - it`s pretty obvious that you can`t avoid such vertices in any shortest path. Complexity of this solution is two times from Dijkstra algo (depending from implementation O(V^2) or O(V * log(V) + E * log(V)) using some kind of heap) + in worst case V checks for each vertices in first found shortest path

My solution is here

kssp library, part 2

Previous part 

I was struck by the idea of how to reduce size of graph before enumerating all K-th shortest paths. We can use cut-points. By definition if we have cut-point in some shortest path it must be visited always - otherwise you can`t reach the destination. So algo is simple

1. find with Dijkstra algo first shortest paths for whole graph
2. find all cut-points in whole graph
3. iterate over found shortest path - if current vertex is cut-point - we can run brute-force from previous cut-point till current

Results are crazy anyway - on the same test 7

• Yen: 13.86s, 29787, 3501 cycles
• Node Classification: 118.4s, 30013, 3501 cycles
• Postponed Node Classification: 104.95s, 30013, 3501 cycles
  
• PNC*: 120.33s, 30013, 3501 cycles
  
• Parsimonious Sidetrack Based: 4.66s, 29980, 3501 cycles
  
• Parsimonious Sidetrack Based v2: 4.79s, 29980, 3501 cycles
  
• Parsimonious Sidetrack Based v3: 4.85s, 29980, 3501 cycles
  
• Sidetrack Based: 4.18s, 29980, 3501 cycles
  
• Sidetrack Based with update: 4.34s, 29980, 3501 cycles
  

At this time all algos worked to completion and again gave different results...
Source code

kssp library

I`ve tried to solve CSES task "visiting cities"

Looks like you can use kind of brute-force - get 1st shortest paths, then all remained with the same cost and make union of cities in each path - nor elegant nor smart algorithm, just to estimate if this approach works at all

I remember from my university course "graph theory" about Yen`s algo to get K-th shortest path so choosed to use some ready (and hopefully well-tested) implementation - kssp library from INRIA (yep - famous place where OCaml was invented)

And then happened real madness - different algos gave me different result and moreover - they didn't match with "correct" results from CSES! Lets see what I got (all results for test 7, compilation options -O3 -DTIME -DNDEBUG):

• Yen - 470s, 30157 cities
• node classification - 4.37s, 30140 cities
• postponed node classification - 3.83s, 30140 cities
• postponed node classification with star - 3.76s, 30140 cities
• sidetrack based - consumed 13Gb of memory and met with OOM killer
  
• parsimonious sidetrack based - OOM again, perhaps bcs not enough parsimonious :-)
  

Source code

ctf-like task based on maximal clique problem

Sources

There is undirected graph with 1024 vertices and 100909 edges (so average degree is 98.5). It is known that the graph contains clique with size 16. You can pass indexes of clique`s vertices in command line like

./ctf 171 345

./ctf 171 346
too short clique 

This vertices of clique then used to derive AES key and decrypt some short string

Can you solve this?

yet another maximal clique algorithm

It seems that most of known algorithms for maximal clique try to add as much vertices as possibly and evolving towards more complex heuristics for vertices ordering. But there is opposite way - we can remove some vertices from neighbors, right?

Lets assume that we sorted all vertices of graph with M vertices and N edges by their degrees in descending order and want to check if some vertex with degree K can contain clique. We can check if all of it`s neighbors mutually connected and find one or several most loosely connected vertices - lets name it L. This checking requires K -1 access to adjacency matrix for first vertex, K -2 for second etc - in average (K^ 2) / 2. If no unconnected vertices was found - all survived neighbors are clique. See sample of implementation in function naive_remove

Now we should decay what we can do with L and there is only 2 variants:

1. we can remove it from set of neighbors
2. we can keep it and remove from set of neighbors all vertices not connected with L
   

Notice that in both cases amount of neighbors decreased by at least 1. Now we can recursively repeat this process with removed and remained L at most K times, so complexity will be O = (K ^ 2) / 2 * (2 ^ K)

We can repeat this process for all vertices with degree bigger than maximal size of previously found clique - in worse case M times, so overall complexity of this algorithm is O = M * (K ^ 2) / 2 * (2 ^ K)

In average K =  N / M

well, not very good result but processing of each vertex can be done in parallel

We can share adjacency matrix (or even make it read-only) between all working threads and this recursive function will require in each step following memory:

1. bitset of survived neighbors - K / 8 where V[i] is 1 if this vertex belongs to neighbors and 0 if it was removed
   
2. array for unconnected vertices counts with size K

given that recursion level does not exceed K overall used space on stack is

S = K * (K / 8 + K * sizeof(index))

now check if we can run this algorithm on

gpu

Disclaimer: I read book about CUDA programming almost 10 years ago so I can be wrong

estimation of maximum clique size

definition 1.1 from really cool book "The Design of Approximation Algorithms":

An α-approximation algorithm for an optimization problem is a polynomial-time algorithm that for all instances of the problem produces a solution whose value is within a factor of α of the value of an optimal solution

so you need first to estimate at least size of possible optimal solution, right?

Surprisingly I was unable to find it for maximal clique. stackexchange offers very simple formula (spoiler: the actual size is a couple of orders of magnitude smaller). python networkX offers method with complexity O(1.4422ⁿ) to find maximal clique itself only. cool. Let's invent this algorithm by ourselves

From wikipedia:

A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent

in other words this means that graph with maximal clique of size K should contains at least K vertices with degree K - 1 or bigger. So we can arrange vertices on degrees and find some degree S where amount of vertices with degree S or bigger is >= S. But this is very rough estimation and it could be refined taking into account the following observation - we can remove all edges to vertices not belonging to this subgraph. So algo is:

1. calculate degrees of all vertices and arrange them in descending order
2. for each degree S find first where amount of vertices with degree S or bigger is >= S
3. put all such vertices in sub-graph SD
4. remove from SD all edges to vertices not belonging to SD
5. recalculate degrees of all vertices in SD
6. find another degree S in SD where amount of vertices with degree S or bigger is >= S. this will be result R

next we can repeat steps 2-6 until enumerate all degrees or some degree will be less than the previously found result R

Complexity

Let N - amount of vertices and M - amount of edges. Then cycle can run max N times and in each cycle we can remove less that M edges (actually in average M/2), so in worst case complexity is O(MN/2)

Results 

(semi)auto building of state machine

Several days ago I made PoC to extract addresses of WSK data from windows 10 arm64 afd.sys - specifically AfdWskClientListHead and lock AfdWskClientSpinLock. Nothing special except fact that afd.sys has no exported functions. So you must find some rare constant, then find functions which use it and only then do some disasm applying state machine to each code block (see lambda passed to traverse_simple_state_graph)

While I was writing this code, I was not left with a question whether it is possible to employ computer to build such state machines. And now I know that this is possible (at least for code on plain C for RISC-like asm with predictable addresses of instructions etc etc)

Lets see how such algo can be arranged:

1) you must find all cross-refs to desired variable and collect list of functions which use it (exactly what deriv_hack::find_xrefs method does)

2) then you must disasm each such function and try to get some primitives - like loading of constants, calling imported/exported functions etc - see deriv_hack::make_path method. Sure set of this primitives will be different for each processor and perhaps will depends from your tasks

Results for afd.sys!AfdWskClientListHead:

The Garbage Collection Handbook

I finished reading this book today
This is just incredible useful book especially if you writing application-specific heap-spray detectors

Site
Bibliography
Glossary

bug in "The Algorithm Design Manual", Second Edition ?

Сitation from subchapter 8.7.2 When are Dynamic Programming Algorithms Efficient? on page 315:

Let LP' [i, j, S] denote the longest simple path from i to j, where the intermediate vertices on this path are exactly those in the subset S. Thus, if S = {a, b, c}, there are exactly six paths
consistent with S: iabcj, iacbj, ibacj, ibcaj, icabj, and icbaj. This state space is at most 2**n, and thus smaller than enumerating the paths

Wait, if this is exponent we must have 2 ** 3 = 8 paths. But actually this is factorial ! Why Skiena claims that this is exponent ?

binary tree for multithread access

Task
I need some binary tree structure for concurrent access from multiple threads where some threads do searching and some other perform insert/delete operations. This structure must work both in kernel and user mode

Solutions
Lets add some sync primitive to each tree node -  it is going to be SRWLock in user mode and EX_PUSH_LOCK in kernel mode. It`s clear that reader can acquire shared lock while writer will use exclusive one. Bcs order of locks always have to be the same - we need tree structure with top-down rebalancing (I hope this is right assumption). So lets see which kinds of trees allow such operations

1. weight-balanced tree. Drawbacks: need to use floating point, so in kernel mode we must care about FPU context saving/restoring
2. classical B-tree. I think there may be a problem with granularity - when node contains a big number of keys and we need to lock it exclusively - all search operations will be blocked from this node till the lowest level of its children
3. red-black tree. Looks like it is a good candidate but sadly I cannot find implementation in plain C with top-down rebalancing :-(

Do I miss something important ?

Art of Concurrency

я канешна давно забыл закон Ома все те крайне немногочисленные алгоритмы, которым меня пытались научить во времена молодости царя гороха, но есть мнение, что алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна реализован в главе 6 дико неоптимально. Например совершенно непонятно зачем выделять массив целых чисел markS чтобы положить туда флаг принадлежности к множеству. Меня например также учили, что выделение памяти достаточно дорогая операция и в данном случае можно было бы обойтись без нее, переписав функцию ArrayPack без использования этого массива с парой лишних сравнений для каждого элемента. Кроме того, выделенная память нигде не освобождается.
Что еще угарнее - название использованного алгоритма так и не приводится в книжке. Пребываю в легком недоумении

Update: а реализация барьеров в главе 7 совершенно безобразна. Вместо того чтобы сначала взвести все переменные и только потом вызывать pthread_cond_broadcast, гражданин вводит лишнюю сущность color. Только это не работает
Предположим что после вызова pthread_cond_broadcast текущий поток вытесняется и один из проснувшихся потоков повторно входит в барьер, уменьшая значение счетчика (который становится -1). Поток соотв-но встает на pthread_cond_wait. Затем исходный поток оживает, сбрасывает count в numThreads и идет по своим делам. Итого - один поток потерялся навсегда и
все последующие потоки будут тупить на его реализации барьера вечно
И еще было бы неплохо объявить поле numThreads в структуре pth_barrier_t как volatile, а то малоличо

mathcad

ставил сегодня весь день subj под 64битную w7
Адовый совершенно квест

• сначала инсталлятор просто падал в самом начале. Гугл сказал что имя компутера не должно содержать проклятый рюсский пукфы
• потом оно сказало мне человеческим голосом что ей нужен msxml4 sp2. Это на живой windows7 !

Отвратительно, но поставил кажется за четыре часа

book needed

А вот например на старости лет возникла нужда освежить знания по теории графов и прочих недобитых князьев
Поскольку предмет тяжек и времени не особо дофига на чтение - нужна ровно одна тонкая книжка, в которой были бы описаны совершенно конкретные алгоритмы потокового анализа и преобразования программ например
Из ваших интернетов нашел следующие варианты:

1. "Graph Theory with Applications" J.A.Bondy & U.S.R.Murty
2. "Approximation Algorithms for NP-Hard Problems" D.S.Hochbaum
3. на русском - В. Н. Касьянов, В. А. Евстигнеев "Графы в программировании: обработка, визуализация и применение". Но они какой-то совершенно упячечный язык для описания алгоритмов используют

Какая из ? Или есть более другие варианты ?

а как сюда математические формулы вставлять

со всякими символами типа пересечения множеств и проч ? Вот например копирую я всякое умное из pdf - и вместо всяких греческих букв, индексов и прочих стандартных математических знаков и операций вижу только совершенно одинаковые знаки вопроса
это все патамушта кровожадный педераст боженька ненавидит меня ялузир, да ?

Why Programs Fail. A Guide to Systematic Debugging

отличная книжка например - в ней прекрасно все кроме попсового названия (честно говоря из-за названия я едва не решил ее не читать вовсе - думал что это очередной сборник малосвязанных паттернов типа Memory Dump Analysis Anthology)
Автор с переменным успехом скрупулезно описывает инструменты и техники, позволяющие максимально автоматизировать процесс нахождения источников ошибок. Правда многие инструменты либо маргинальны (т.е. далеко не mainstream), либо требуют кучи ресурсов, либо применимы только в ограниченном числе случаев.

Вот например в главе 13.6 описывается fuzzer для планировщика потоков под названием dejavu (Java only). Для отладки весьма небольшого куска кода (733 строки, если выкинуть все не относящееся к делу - 6 строчек) получается 3.8 миллиарда различающихся состояний. Хотя и утверждается что алгоритм O(log) и автоматически нашел комбинацию исполнения потоков, приводящую к ошибке, всего за 50 тестов - у меня есть обоснованные сомнения что это хорошо будет масштабироваться на более-менее реальных примерах. C другой стороны подобный scheduling fuzzer был бы ацки полезен для нахождения race conditions

Глава 7 содержит очень полезные техники для статического анализа кода, а также его фундаментальные ограничения.
Глава 10 посвящена разнообразным динамическим проверкам - от обычного assert до valgrind & purify

Перечислю инструменты, показавшиеся мне особенно полезными:

• FAUMachine is a virtual machine specifically built for testing purposes. Among others, the FAUMachine allows you to control the entire virtual machine via scripts
• codesurfer - анализатор исходников, умеющий показывать пути в графе codeflow, где переменная изменяется и где используется
• ODB - т.н. omniscient debugger. Способен прокрутить сохраненное состояние отлаживаемой программы как вперед, так и назад, с любого момента
• tarantula - для визуализации исполнившихся кусков кода, отличающихся при нормальном и содержащем дефект запусках

дочитал C++ Concurrency in Action

был неиллюзорно поражен скудностью и лаконичностью главы 10 - Testing and Debugging Multithreaded Applications

Автор упоминает про combination simulation testing - идея в том чтобы протестировать все возможные комбинации всех локов всеми потоками на симуляторе. Несложно догадаться что сложность этого алгоритма O(N!), где N - сумма потоков и объектов блокировки, и вряд ли когда-нибудь этот метод будет реализован на практике. Однако - на самом деле нам не нужно прогонять все возможные комбинации при тестировании некоего куска кода - в большинстве случаев достаточно всего лишь прогнать все возможные комбинации одновременно работающих потоков, что на машине с n камнями и N потоками (как правило N > n) дает нам подмножества n конечных множеств из N (биномиальный коэффициент, ага). Практически этого можно достигнуть например применяя под linux соответствующим образом написанный планировщик - нужно дописать к нему интерфейс общения из user mode и ровно 3 ioctls:

• поместить некий поток в группу
• запустить перебор на одновременное исполнение для всех потоков в группе
• сообщить результаты перебора (готово-неготово-сколько циклов прогнано)

Также автор упоминает про tests with special library, но из целой одной странички, посвященной изложению темы, можно почерпнуть мало чего. Однако - это крайне богатая идея, например можно придумать достаточно простой алгоритм для нахождения взаимной блокировки потоков. Пусть у нас есть два три потока - A, B и С, и скажем поток C делает join к потоку B, поток B делает join к потоку A, а поток A собирается сделать join с потоку C, что даст в результате вечный deadlock. Нет ничего проще - заводим внешний орграф, в нем узлы - потоки, а операции join - ребра, при добавлении нового ребра проверяем граф на наличие циклов. Если цикл обнаружен - у нас deadlock в коде

Аналогично можно находить взаимоблокировки - например в каждом потоке вести множество залоченных объектов и объектов, которые поток пытается залочить. Пусть например есть два потока

• A, залочивший mutex a и пытающийся залочить mutex b
• поток B, залочивший mutex b и висящий на ожидании mutex a. 

По моему для случая двух потоков нахождение таких взаимоблокировок - совершенно тривиальная задача. Или можно представлять объекты синхронизации как узлы графа, а использующие их потоки - как ребра (например в вышеописанном примере поток A будет ребром между mutexes a & b, а поток B - ребром между b & a). Нахождение взаимоблокировки в таком случае - поиск циклов графа, составленных из ребер разных потоков.