Markov::API::ModelMatrix Class Reference

Class to flatten and reduce Markov::Model to a Matrix. More...

#include <modelMatrix.h>

Inheritance diagram for Markov::API::ModelMatrix:

Collaboration diagram for Markov::API::ModelMatrix:

Public Member Functions
	ModelMatrix ()
bool	ConstructMatrix ()
	Construct the related Matrix data for the model. More...
void	DumpJSON ()
	Debug function to dump the model to a JSON file. More...
int	FastRandomWalk (unsigned long int n, const char *wordlistFileName, int minLen=6, int maxLen=12, int threads=20, bool bFileIO=true)
	Random walk on the Matrix-reduced Markov::Model. More...
void	Import (const char *filename)
	Open a file to import with filename, and call bool Model::Import with std::ifstream. More...
void	Train (const char *datasetFileName, char delimiter, int threads)
	Train the model with the dataset file. More...
std::ifstream *	OpenDatasetFile (const char *filename)
	Open dataset file and return the ifstream pointer. More...
std::ofstream *	Save (const char *filename)
	Export model to file. More...
void	Generate (unsigned long int n, const char *wordlistFileName, int minLen=6, int maxLen=12, int threads=20)
	Call Markov::Model::RandomWalk n times, and collect output. More...
void	Buff (const char *str, double multiplier, bool bDontAdjustSelfLoops=true, bool bDontAdjustExtendedLoops=false)
	Buff expression of some characters in the model. More...
char *	RandomWalk (Markov::Random::RandomEngine *randomEngine, int minSetting, int maxSetting, char *buffer)
	Do a random walk on this model. More...
void	AdjustEdge (const char *payload, long int occurrence)
	Adjust the model with a single string. More...
bool	Import (std::ifstream *)
	Import a file to construct the model. More...
bool	Export (std::ofstream *)
	Export a file of the model. More...
bool	Export (const char *filename)
	Open a file to export with filename, and call bool Model::Export with std::ofstream. More...
Node< char > *	StarterNode ()
	Return starter Node. More...
std::vector< Edge< char > * > *	Edges ()
	Return a vector of all the edges in the model. More...
std::map< char, Node< char > * > *	Nodes ()
	Return starter Node. More...
void	OptimizeEdgeOrder ()
	Sort edges of all nodes in the model ordered by edge weights. More...

Protected Member Functions
int	FastRandomWalk (unsigned long int n, std::ofstream *wordlist, int minLen=6, int maxLen=12, int threads=20, bool bFileIO=true)
	Random walk on the Matrix-reduced Markov::Model. More...
void	FastRandomWalkPartition (std::mutex *mlock, std::ofstream *wordlist, unsigned long int n, int minLen, int maxLen, bool bFileIO, int threads)
	A single partition of FastRandomWalk event. More...
void	FastRandomWalkThread (std::mutex *mlock, std::ofstream *wordlist, unsigned long int n, int minLen, int maxLen, int id, bool bFileIO)
	A single thread of a single partition of FastRandomWalk. More...
bool	DeallocateMatrix ()
	Deallocate matrix and make it ready for re-construction. More...

Protected Attributes
char **	edgeMatrix
	2-D Character array for the edge Matrix (The characters of Nodes) More...
long int **	valueMatrix
	2-d Integer array for the value Matrix (For the weights of Edges) More...
int	matrixSize
	to hold Matrix size More...
char *	matrixIndex
	to hold the Matrix index (To hold the orders of 2-D arrays') More...
long int *	totalEdgeWeights
	Array of the Total Edge Weights. More...
bool	ready
	True when matrix is constructed. False if not. More...

Private Member Functions
void	TrainThread (Markov::API::Concurrency::ThreadSharedListHandler *listhandler, char delimiter)
	A single thread invoked by the Train function. More...
void	GenerateThread (std::mutex *outputLock, unsigned long int n, std::ofstream *wordlist, int minLen, int maxLen)
	A single thread invoked by the Generate function. More...

Private Attributes
std::ifstream *	datasetFile
std::ofstream *	modelSavefile
	Dataset file input of our system More...
std::ofstream *	outputFile
	File to save model of our system More...
std::map< char, Node< char > * >	nodes
	Map LeftNode is the Nodes NodeValue Map RightNode is the node pointer. More...
Node< char > *	starterNode
	Starter Node of this model. More...
std::vector< Edge< char > * >	edges
	A list of all edges in this model. More...

Detailed Description

Class to flatten and reduce Markov::Model to a Matrix.

Matrix level operations can be used for Generation events, with a significant performance optimization at the cost of O(N) memory complexity (O(1) memory space for slow mode)

To limit the maximum memory usage, each generation operation is partitioned into 50M chunks for allocation. Threads are sychronized and files are flushed every 50M operations.

Definition at line 23 of file modelMatrix.h.

Constructor & Destructor Documentation

ModelMatrix()

Markov::API::ModelMatrix::ModelMatrix

(

)

Definition at line 15 of file modelMatrix.cpp.

                                 {
    this->ready = false;
}

References ready.

Member Function Documentation

AdjustEdge()

void Markov::Model< char >::AdjustEdge ( const NodeStorageType *  payload, long int  occurrence  )

inherited

Adjust the model with a single string.

Start from the starter node, and for each character, AdjustEdge the edge EdgeWeight from current node to the next, until NULL character is reached.

Then, update the edge EdgeWeight from current node, to the terminator node.

This function is used for training purposes, as it can be used for adjusting the model with each line of the corpus file.

Example Use: Create an empty model and train it with string: "testdata"

Markov::Model<char> model;
char test[] = "testdata";
model.AdjustEdge(test, 15); 

Parameters

string	- String that is passed from the training, and will be used to AdjustEdge the model with
occurrence	- Occurrence of this string.

Definition at line 109 of file model.h.

                                                                                                 {
    NodeStorageType p = payload[0];
    Markov::Node<NodeStorageType>* curnode = this->starterNode;
    Markov::Edge<NodeStorageType>* e;
    int i = 0;
 
    if (p == 0) return;
    while (p != 0) {
        e = curnode->FindEdge(p);
        if (e == NULL) return;
        e->AdjustEdge(occurrence);
        curnode = e->RightNode();
        p = payload[++i];
    }
 
    e = curnode->FindEdge('\xff');
    e->AdjustEdge(occurrence);
    return;
}

Buff()

void Markov::API::MarkovPasswords::Buff ( const char *  str, double  multiplier, bool  bDontAdjustSelfLoops = true, bool  bDontAdjustExtendedLoops = false  )

inherited

Buff expression of some characters in the model.

Parameters

str	A string containing all the characters to be buffed
multiplier	A constant value to buff the nodes with.
bDontAdjustSelfEdges	Do not adjust weights if target node is same as source node
bDontAdjustExtendedLoops	Do not adjust if both source and target nodes are in first parameter

Definition at line 153 of file markovPasswords.cpp.

                                                                                                                               {
    std::string buffstr(str);
    std::map< char, Node< char > * > *nodes;
    std::map< char, Edge< char > * > *edges;
    nodes = this->Nodes();
    int i=0;
    for (auto const& [repr, node] : *nodes){
        edges = node->Edges();
        for (auto const& [targetrepr, edge] : *edges){
            if(buffstr.find(targetrepr)!= std::string::npos){
                if(bDontAdjustSelfLoops && repr==targetrepr) continue;
                if(bDontAdjustExtendedLoops){
                    if(buffstr.find(repr)!= std::string::npos){
                        continue;
                    }
                }
                long int weight = edge->EdgeWeight();
                weight = weight*multiplier;     
                edge->AdjustEdge(weight);
            }
 
        }
        i++;
    }
 
    this->OptimizeEdgeOrder();
}

References Markov::Edge< NodeStorageType >::AdjustEdge(), Markov::Node< storageType >::Edges(), Markov::Edge< NodeStorageType >::EdgeWeight(), Markov::Model< NodeStorageType >::Nodes(), and Markov::Model< NodeStorageType >::OptimizeEdgeOrder().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

ConstructMatrix()

bool Markov::API::ModelMatrix::ConstructMatrix

(

)

Construct the related Matrix data for the model.

This operation can be used after importing/training to allocate and populate the matrix content.

this will initialize: char** edgeMatrix -> a 2D array of mapping left and right connections of each edge. long int **valueMatrix -> a 2D array representing the edge weights. int matrixSize -> Size of the matrix, aka total number of nodes. char* matrixIndex -> order of nodes in the model long int *totalEdgeWeights -> total edge weights of each Node.

Returns

True if constructed. False if already construced.

Definition at line 31 of file modelMatrix.cpp.

                                          {
    if(this->ready) return false;
    this->matrixSize = this->StarterNode()->edgesV.size() + 2;
 
    this->matrixIndex = new char[this->matrixSize];
    this->totalEdgeWeights = new long int[this->matrixSize];
 
    this->edgeMatrix = new char*[this->matrixSize];
    for(int i=0;i<this->matrixSize;i++){
        this->edgeMatrix[i] = new char[this->matrixSize];
    }
    this->valueMatrix = new long int*[this->matrixSize];
    for(int i=0;i<this->matrixSize;i++){
        this->valueMatrix[i] = new long int[this->matrixSize];
    }
    std::map< char, Node< char > * > *nodes;
    nodes = this->Nodes();
    int i=0;
    for (auto const& [repr, node] : *nodes){
        if(repr!=0) this->matrixIndex[i] = repr;
        else this->matrixIndex[i] = 199;
        this->totalEdgeWeights[i] = node->TotalEdgeWeights();
        for(int j=0;j<this->matrixSize;j++){
            char val = node->NodeValue();
            if(val < 0){
                for(int k=0;k<this->matrixSize;k++){
                    this->valueMatrix[i][k] = 0;
                    this->edgeMatrix[i][k] = 255;
                }
                break;
            }
            else if(node->NodeValue() == 0 && j>(this->matrixSize-3)){
                this->valueMatrix[i][j] = 0;
                this->edgeMatrix[i][j] = 255;
            }else if(j==(this->matrixSize-1)) {
                this->valueMatrix[i][j] = 0;
                this->edgeMatrix[i][j] = 255;
            }else{
                this->valueMatrix[i][j] = node->edgesV[j]->EdgeWeight();
                this->edgeMatrix[i][j]  = node->edgesV[j]->RightNode()->NodeValue();
            }
 
        }
        i++;
    }
    this->ready = true;
    return true;
    //this->DumpJSON();
}

References edgeMatrix, Markov::Edge< NodeStorageType >::EdgeWeight(), matrixIndex, matrixSize, Markov::Model< NodeStorageType >::Nodes(), Markov::Node< storageType >::NodeValue(), ready, Markov::Edge< NodeStorageType >::RightNode(), Markov::Model< NodeStorageType >::StarterNode(), totalEdgeWeights, Markov::Node< storageType >::TotalEdgeWeights(), and valueMatrix.

Referenced by Markov::Markopy::CUDA::BOOST_PYTHON_MODULE(), Markov::Markopy::BOOST_PYTHON_MODULE(), Import(), and Train().

Here is the call graph for this function:

Here is the caller graph for this function:

DeallocateMatrix()

bool Markov::API::ModelMatrix::DeallocateMatrix ( )

protected

Deallocate matrix and make it ready for re-construction.

Returns

True if deallocated. False if matrix was not initialized

Definition at line 81 of file modelMatrix.cpp.

                                           {
    if(!this->ready) return false;
    delete[] this->matrixIndex;
    delete[] this->totalEdgeWeights;
 
    for(int i=0;i<this->matrixSize;i++){
        delete[] this->edgeMatrix[i];
    }
    delete[] this->edgeMatrix;
 
    for(int i=0;i<this->matrixSize;i++){
        delete[] this->valueMatrix[i];
    }
    delete[] this->valueMatrix;
 
    this->matrixSize = -1;
    this->ready = false;
    return true;
}

References edgeMatrix, matrixIndex, matrixSize, ready, totalEdgeWeights, and valueMatrix.

Referenced by Import(), and Train().

Here is the caller graph for this function:

DumpJSON()

void Markov::API::ModelMatrix::DumpJSON

(

)

Debug function to dump the model to a JSON file.

Might not work 100%. Not meant for production use.

Definition at line 101 of file modelMatrix.cpp.

                                   {
 
    std::cout << "{\n   \"index\": \"";
    for(int i=0;i<this->matrixSize;i++){
        if(this->matrixIndex[i]=='"') std::cout << "\\\"";
        else if(this->matrixIndex[i]=='\\') std::cout << "\\\\";
        else if(this->matrixIndex[i]==0) std::cout << "\\\\x00";
        else if(i==0) std::cout << "\\\\xff";
        else if(this->matrixIndex[i]=='\n') std::cout << "\\n";
        else std::cout << this->matrixIndex[i];
    }
    std::cout << 
    "\",\n"
    "   \"edgemap\": {\n";
 
    for(int i=0;i<this->matrixSize;i++){
        if(this->matrixIndex[i]=='"') std::cout << "      \"\\\"\": [";
        else if(this->matrixIndex[i]=='\\') std::cout << "      \"\\\\\": [";
        else if(this->matrixIndex[i]==0) std::cout << "      \"\\\\x00\": [";
        else if(this->matrixIndex[i]<0) std::cout << "      \"\\\\xff\": [";
        else std::cout << "      \"" << this->matrixIndex[i] << "\": [";
        for(int j=0;j<this->matrixSize;j++){
            if(this->edgeMatrix[i][j]=='"') std::cout << "\"\\\"\"";
            else if(this->edgeMatrix[i][j]=='\\') std::cout << "\"\\\\\"";
            else if(this->edgeMatrix[i][j]==0) std::cout << "\"\\\\x00\"";
            else if(this->edgeMatrix[i][j]<0) std::cout << "\"\\\\xff\"";
            else if(this->matrixIndex[i]=='\n') std::cout << "\"\\n\"";
            else std::cout << "\"" << this->edgeMatrix[i][j] << "\"";
            if(j!=this->matrixSize-1) std::cout << ", ";
        }
        std::cout << "],\n";
    }
    std::cout << "},\n";
 
    std::cout << "\"   weightmap\": {\n";
    for(int i=0;i<this->matrixSize;i++){
        if(this->matrixIndex[i]=='"') std::cout << "      \"\\\"\": [";
        else if(this->matrixIndex[i]=='\\') std::cout << "      \"\\\\\": [";
        else if(this->matrixIndex[i]==0) std::cout << "      \"\\\\x00\": [";
        else if(this->matrixIndex[i]<0) std::cout << "      \"\\\\xff\": [";
        else std::cout << "      \"" << this->matrixIndex[i] << "\": [";
 
        for(int j=0;j<this->matrixSize;j++){
            std::cout << this->valueMatrix[i][j];
            if(j!=this->matrixSize-1) std::cout << ", ";
        }
        std::cout << "],\n";
    }
    std::cout << "  }\n}\n";
}

References edgeMatrix, matrixIndex, matrixSize, and valueMatrix.

Referenced by Markov::Markopy::CUDA::BOOST_PYTHON_MODULE(), and Markov::Markopy::BOOST_PYTHON_MODULE().

Here is the caller graph for this function:

Edges()

std::vector<Edge<char >*>* Markov::Model< char >::Edges ( )

inlineinherited

Return a vector of all the edges in the model.

Returns

vector of edges

Definition at line 176 of file model.h.

{ return &edges;}

Export() [1/2]

bool Markov::Model< char >::Export ( const char *  filename )

inherited

Open a file to export with filename, and call bool Model::Export with std::ofstream.

Returns

True if successful, False for incomplete models or corrupt file formats

Example Use: Export file to filename

Markov::Model<char> model;
model.Export("test.mdl");

Definition at line 166 of file model.h.

                                                              {
    std::ofstream exportfile;
    exportfile.open(filename);
    return this->Export(&exportfile);
}

Export() [2/2]

bool Markov::Model< char >::Export ( std::ofstream *  f )

inherited

Export a file of the model.

File contains a list of edges. Format is: Left_repr;EdgeWeight;right_repr. For more information on the format, check out the project wiki or github readme.

Iterate over this vertices, and their edges, and write them to file.

Returns

True if successful, False for incomplete models.

Example Use: Export file to ofstream

Markov::Model<char> model;
std::ofstream file("test.mdl");
model.Export(&file);

Definition at line 155 of file model.h.

                                                        {
    Markov::Edge<NodeStorageType>* e;
    for (std::vector<int>::size_type i = 0; i != this->edges.size(); i++) {
        e = this->edges[i];
        //std::cout << e->LeftNode()->NodeValue() << "," << e->EdgeWeight() << "," << e->RightNode()->NodeValue() << "\n";
        *f << e->LeftNode()->NodeValue() << "," << e->EdgeWeight() << "," << e->RightNode()->NodeValue() << "\n";
    }
 
    return true;
}

FastRandomWalk() [1/2]

int Markov::API::ModelMatrix::FastRandomWalk	(	unsigned long int	n,
		const char *	wordlistFileName,
		int	minLen = 6,
		int	maxLen = 12,
		int	threads = 20,
		bool	bFileIO = true
	)

Random walk on the Matrix-reduced Markov::Model.

This has an O(N) Memory complexity. To limit the maximum usage, requests with n>50M are partitioned using Markov::API::ModelMatrix::FastRandomWalkPartition.

If n>50M, threads are going to be synced, files are going to be flushed, and buffers will be reallocated every 50M generations. This comes at a minor performance penalty.

While it has the same functionality, this operation reduces Markov::API::MarkovPasswords::Generate runtime by %96.5

This function has deprecated Markov::API::MarkovPasswords::Generate, and will eventually replace it.

Parameters

n	- Number of passwords to generate.
wordlistFileName	- Filename to write to
minLen	- Minimum password length to generate
maxLen	- Maximum password length to generate
threads	- number of OS threads to spawn
bFileIO	- If false, filename will be ignored and will output to stdout.

Markov::API::ModelMatrix mp;
mp.Import("models/finished.mdl");
mp.FastRandomWalk(50000000,"./wordlist.txt",6,12,25, true);

Definition at line 217 of file modelMatrix.cpp.

                                                                                                                                            {
    std::ofstream wordlist; 
    if(bFileIO)
        wordlist.open(wordlistFileName);
    this->FastRandomWalk(n, &wordlist, minLen, maxLen, threads, bFileIO);
    return 0;
}

References FastRandomWalk().

Referenced by Markov::Markopy::BOOST_PYTHON_MODULE().

Here is the call graph for this function:

Here is the caller graph for this function:

FastRandomWalk() [2/2]

int Markov::API::ModelMatrix::FastRandomWalk ( unsigned long int  n, std::ofstream *  wordlist, int  minLen = 6, int  maxLen = 12, int  threads = 20, bool  bFileIO = true  )

protected

Random walk on the Matrix-reduced Markov::Model.

This has an O(N) Memory complexity. To limit the maximum usage, requests with n>50M are partitioned using Markov::API::ModelMatrix::FastRandomWalkPartition.

If n>50M, threads are going to be synced, files are going to be flushed, and buffers will be reallocated every 50M generations. This comes at a minor performance penalty.

While it has the same functionality, this operation reduces Markov::API::MarkovPasswords::Generate runtime by %96.5

This function has deprecated Markov::API::MarkovPasswords::Generate, and will eventually replace it.

Parameters

n	- Number of passwords to generate.
wordlistFileName	- Filename to write to
minLen	- Minimum password length to generate
maxLen	- Maximum password length to generate
threads	- number of OS threads to spawn
bFileIO	- If false, filename will be ignored and will output to stdout.

Markov::API::ModelMatrix mp;
mp.Import("models/finished.mdl");
mp.FastRandomWalk(50000000,"./wordlist.txt",6,12,25, true);

Definition at line 204 of file modelMatrix.cpp.

                                                                                                                                     {
    
 
    std::mutex mlock;
    if(n<=50000000ull) this->FastRandomWalkPartition(&mlock, wordlist, n, minLen, maxLen, bFileIO, threads);
    else{
        int numberOfPartitions = n/50000000ull;
        for(int i=0;i<numberOfPartitions;i++)
            this->FastRandomWalkPartition(&mlock, wordlist, 50000000ull, minLen, maxLen, bFileIO, threads);
    }
    return 0;
}

References FastRandomWalkPartition().

Referenced by FastRandomWalk().

Here is the call graph for this function:

Here is the caller graph for this function:

FastRandomWalkPartition()

void Markov::API::ModelMatrix::FastRandomWalkPartition ( std::mutex *  mlock, std::ofstream *  wordlist, unsigned long int  n, int  minLen, int  maxLen, bool  bFileIO, int  threads  )

protected

A single partition of FastRandomWalk event.

Since FastRandomWalk has to allocate its output buffer before operation starts and writes data in chunks, large n parameters would lead to huge memory allocations. Without Partitioning:

• 50M results 12 characters max -> 550 Mb Memory allocation
• 5B results 12 characters max -> 55 Gb Memory allocation
• 50B results 12 characters max -> 550GB Memory allocation

Instead, FastRandomWalk is partitioned per 50M generations to limit the top memory need.

Parameters

mlock	- mutex lock to distribute to child threads
wordlist	- Reference to the wordlist file to write to
n	- Number of passwords to generate.
wordlistFileName	- Filename to write to
minLen	- Minimum password length to generate
maxLen	- Maximum password length to generate
threads	- number of OS threads to spawn
bFileIO	- If false, filename will be ignored and will output to stdout.

Definition at line 225 of file modelMatrix.cpp.

                                                                                                                                                                {
    
    int iterationsPerThread = n/threads;
    int iterationsPerThreadCarryOver = n%threads;
 
    std::vector<std::thread*> threadsV;
    
    int id = 0;
    for(int i=0;i<threads;i++){
        threadsV.push_back(new std::thread(&Markov::API::ModelMatrix::FastRandomWalkThread, this, mlock, wordlist, iterationsPerThread, minLen, maxLen, id, bFileIO));
        id++;
    }
 
    threadsV.push_back(new std::thread(&Markov::API::ModelMatrix::FastRandomWalkThread, this, mlock, wordlist, iterationsPerThreadCarryOver, minLen, maxLen, id, bFileIO));
 
    for(int i=0;i<threads;i++){
        threadsV[i]->join();
    }
}

References FastRandomWalkThread().

Referenced by FastRandomWalk().

Here is the call graph for this function:

Here is the caller graph for this function:

FastRandomWalkThread()

void Markov::API::ModelMatrix::FastRandomWalkThread ( std::mutex *  mlock, std::ofstream *  wordlist, unsigned long int  n, int  minLen, int  maxLen, int  id, bool  bFileIO  )

protected

A single thread of a single partition of FastRandomWalk.

A FastRandomWalkPartition will initiate as many of this function as requested.

This function contains the bulk of the generation algorithm.

Parameters

mlock	- mutex lock to distribute to child threads
wordlist	- Reference to the wordlist file to write to
n	- Number of passwords to generate.
wordlistFileName	- Filename to write to
minLen	- Minimum password length to generate
maxLen	- Maximum password length to generate
id	- DEPRECATED Thread id - No longer used
bFileIO	- If false, filename will be ignored and will output to stdout.

Definition at line 153 of file modelMatrix.cpp.

                                                                                                                                                        {
    if(n==0) return;
 
    Markov::Random::Marsaglia MarsagliaRandomEngine;
    char* e;
    char *res = new char[(maxLen+2)*n];
    int index = 0;
    char next;
    int len=0;
    long int selection;
    char cur;
    long int bufferctr = 0;
    for (int i = 0; i < n; i++) {
        cur=199;
        len=0;
        while (true) {
            e = strchr(this->matrixIndex, cur);
            index = e - this->matrixIndex;
            selection = MarsagliaRandomEngine.random() % this->totalEdgeWeights[index];
            for(int j=0;j<this->matrixSize;j++){
                selection -= this->valueMatrix[index][j];
                if (selection < 0){
                    next = this->edgeMatrix[index][j];
                    break;
                }
            }
 
            if (len >= maxLen)  break;
            else if ((next < 0) && (len < minLen)) continue;
            else if (next < 0) break;  
            cur = next;
            res[bufferctr + len++] = cur;
        }
        res[bufferctr + len++] = '\n';
        bufferctr+=len;
        
    }
    if(bFileIO){
        mlock->lock();
        *wordlist << res;
        mlock->unlock();
    }else{
        mlock->lock();
        std::cout << res;
        mlock->unlock();
    }
    delete res;
 
}

References edgeMatrix, matrixIndex, matrixSize, Markov::Random::Marsaglia::random(), totalEdgeWeights, and valueMatrix.

Referenced by FastRandomWalkPartition().

Here is the call graph for this function:

Here is the caller graph for this function:

Generate()

void Markov::API::MarkovPasswords::Generate ( unsigned long int  n, const char *  wordlistFileName, int  minLen = 6, int  maxLen = 12, int  threads = 20  )

inherited

Call Markov::Model::RandomWalk n times, and collect output.

Generate from model and write results to a file. a much more performance-optimized method. FastRandomWalk will reduce the runtime by %96.5 on average.

Deprecated:

See Markov::API::MatrixModel::FastRandomWalk for more information.

Parameters

n	- Number of passwords to generate.
wordlistFileName	- Filename to write to
minLen	- Minimum password length to generate
maxLen	- Maximum password length to generate
threads	- number of OS threads to spawn

Definition at line 118 of file markovPasswords.cpp.

                                                                                                                               {
    char* res;
    char print[100];
    std::ofstream wordlist; 
    wordlist.open(wordlistFileName);
    std::mutex mlock;
    int iterationsPerThread = n/threads;
    int iterationsCarryOver = n%threads;
    std::vector<std::thread*> threadsV;
    for(int i=0;i<threads;i++){
        threadsV.push_back(new std::thread(&Markov::API::MarkovPasswords::GenerateThread, this, &mlock, iterationsPerThread, &wordlist, minLen, maxLen));
    }
 
    for(int i=0;i<threads;i++){
        threadsV[i]->join();
        delete threadsV[i];
    }
 
    this->GenerateThread(&mlock, iterationsCarryOver, &wordlist, minLen, maxLen);
    
}

References Markov::API::MarkovPasswords::GenerateThread().

Referenced by Markov::Markopy::BOOST_PYTHON_MODULE(), and Markov::GUI::Generate::generation().

Here is the call graph for this function:

Here is the caller graph for this function:

GenerateThread()

void Markov::API::MarkovPasswords::GenerateThread ( std::mutex *  outputLock, unsigned long int  n, std::ofstream *  wordlist, int  minLen, int  maxLen  )

privateinherited

A single thread invoked by the Generate function.

DEPRECATED: See Markov::API::MatrixModel::FastRandomWalkThread for more information. This has been replaced with a much more performance-optimized method. FastRandomWalk will reduce the runtime by %96.5 on average.

Parameters

outputLock	- shared mutex lock to lock during output operation. Prevents race condition on write.
n	number of lines to be generated by this thread
wordlist	wordlistfile
minLen	- Minimum password length to generate
maxLen	- Maximum password length to generate

Definition at line 140 of file markovPasswords.cpp.

                                                                                                                                       {
    char* res = new char[maxLen+5];
    if(n==0) return;
 
    Markov::Random::Marsaglia MarsagliaRandomEngine;
    for (int i = 0; i < n; i++) {
        this->RandomWalk(&MarsagliaRandomEngine, minLen, maxLen, res); 
        outputLock->lock();
        *wordlist << res << "\n";
        outputLock->unlock();
    }
}

References Markov::Model< NodeStorageType >::RandomWalk().

Referenced by Markov::API::MarkovPasswords::Generate().

Here is the call graph for this function:

Here is the caller graph for this function:

Import() [1/2]

void Markov::API::ModelMatrix::Import

(

const char *

filename

)

Open a file to import with filename, and call bool Model::Import with std::ifstream.

Returns

True if successful, False for incomplete models or corrupt file formats

Example Use: Import a file with filename

Markov::Model<char> model;
model.Import("test.mdl");

Construct the matrix when done.

Definition at line 19 of file modelMatrix.cpp.

                                                     {
    this->DeallocateMatrix();
    this->Markov::API::MarkovPasswords::Import(filename);
    this->ConstructMatrix();
}

References ConstructMatrix(), DeallocateMatrix(), and Markov::Model< NodeStorageType >::Import().

Referenced by Markov::Markopy::CUDA::BOOST_PYTHON_MODULE(), Markov::Markopy::BOOST_PYTHON_MODULE(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

Import() [2/2]

bool Markov::Model< char >::Import ( std::ifstream *  f )

inherited

Import a file to construct the model.

File contains a list of edges. For more info on the file format, check out the wiki and github readme pages. Format is: Left_repr;EdgeWeight;right_repr

Iterate over this list, and construct nodes and edges accordingly.

Returns

True if successful, False for incomplete models or corrupt file formats

Example Use: Import a file from ifstream

Markov::Model<char> model;
std::ifstream file("test.mdl");
model.Import(&file);

Definition at line 126 of file model.h.

                                                        {
    std::string cell;
 
    char src;
    char target;
    long int oc;
 
    while (std::getline(*f, cell)) {
        //std::cout << "cell: " << cell << std::endl;
        src = cell[0];
        target = cell[cell.length() - 1];
        char* j;
        oc = std::strtol(cell.substr(2, cell.length() - 2).c_str(),&j,10);
        //std::cout << oc << "\n";
        Markov::Node<NodeStorageType>* srcN;
        Markov::Node<NodeStorageType>* targetN;
        Markov::Edge<NodeStorageType>* e;
        if (this->nodes.find(src) == this->nodes.end()) {
            srcN = new Markov::Node<NodeStorageType>(src);
            this->nodes.insert(std::pair<char, Markov::Node<NodeStorageType>*>(src, srcN));
            //std::cout << "Creating new node at start.\n";
        }
        else {
            srcN = this->nodes.find(src)->second;
        }
 
        if (this->nodes.find(target) == this->nodes.end()) {
            targetN = new Markov::Node<NodeStorageType>(target);
            this->nodes.insert(std::pair<char, Markov::Node<NodeStorageType>*>(target, targetN));
            //std::cout << "Creating new node at end.\n";
        }
        else {
            targetN = this->nodes.find(target)->second;
        }
        e = srcN->Link(targetN);
        e->AdjustEdge(oc);
        this->edges.push_back(e);
 
        //std::cout << int(srcN->NodeValue()) << " --" << e->EdgeWeight() << "--> " << int(targetN->NodeValue()) << "\n";
 
 
    }
 
    this->OptimizeEdgeOrder();
 
    return true;
}

Nodes()

std::map<char , Node<char >*>* Markov::Model< char >::Nodes ( )

inlineinherited

Return starter Node.

Returns

starter node with 00 NodeValue

Definition at line 181 of file model.h.

{ return &nodes;}

OpenDatasetFile()

std::ifstream * Markov::API::MarkovPasswords::OpenDatasetFile ( const char *  filename )

inherited

Open dataset file and return the ifstream pointer.

Parameters

filename

- Filename to open

Returns

ifstream* to the the dataset file

Definition at line 51 of file markovPasswords.cpp.

                                                                          {
 
    std::ifstream* datasetFile;
 
    std::ifstream newFile(filename);
 
    datasetFile = &newFile;
 
    this->Import(datasetFile);
    return datasetFile;
}

References Markov::Model< NodeStorageType >::Import().

Here is the call graph for this function:

OptimizeEdgeOrder()

void Markov::Model< char >::OptimizeEdgeOrder

inherited

Sort edges of all nodes in the model ordered by edge weights.

Definition at line 186 of file model.h.

                                                    {
    for (std::pair<unsigned char, Markov::Node<NodeStorageType>*> const& x : this->nodes) {
        //std::cout << "Total edges in EdgesV: " << x.second->edgesV.size() << "\n"; 
        std::sort (x.second->edgesV.begin(), x.second->edgesV.end(), [](Edge<NodeStorageType> *lhs, Edge<NodeStorageType> *rhs)->bool{
            return lhs->EdgeWeight() > rhs->EdgeWeight();
        });
        //for(int i=0;i<x.second->edgesV.size();i++)
        //  std::cout << x.second->edgesV[i]->EdgeWeight() << ", ";
        //std::cout << "\n";
    }
    //std::cout << "Total number of nodes: " << this->nodes.size() << std::endl;
    //std::cout << "Total number of edges: " << this->edges.size() << std::endl;
}

RandomWalk()

char * Markov::Model< char >::RandomWalk ( Markov::Random::RandomEngine *  randomEngine, int  minSetting, int  maxSetting, NodeStorageType *  buffer  )

inherited

Do a random walk on this model.

Start from the starter node, on each node, invoke RandomNext using the random engine on current node, until terminator node is reached. If terminator node is reached before minimum length criateria is reached, ignore the last selection and re-invoke randomNext

If maximum length criteria is reached but final node is not, cut off the generation and proceed to the final node. This function takes Markov::Random::RandomEngine as a parameter to generate pseudo random numbers from

This library is shipped with two random engines, Marsaglia and Mersenne. While mersenne output is higher in entropy, most use cases don't really need super high entropy output, so Markov::Random::Marsaglia is preferable for better performance.

This function WILL NOT reallocate buffer. Make sure no out of bound writes are happening via maximum length criteria.

Example Use: Generate 10 lines, with 5 to 10 characters, and print the output. Use Marsaglia

Markov::Model<char> model;
Model.import("model.mdl");
char* res = new char[11];
Markov::Random::Marsaglia MarsagliaRandomEngine;
for (int i = 0; i < 10; i++) {
    this->RandomWalk(&MarsagliaRandomEngine, 5, 10, res); 
    std::cout << res << "\n";
 }

Parameters

randomEngine	Random Engine to use for the random walks. For examples, see Markov::Random::Mersenne and Markov::Random::Marsaglia
minSetting	Minimum number of characters to generate
maxSetting	Maximum number of character to generate
buffer	buffer to write the result to

Returns

Null terminated string that was generated.

Definition at line 86 of file model.h.

                                                                                                                                                         {
    Markov::Node<NodeStorageType>* n = this->starterNode;
    int len = 0;
    Markov::Node<NodeStorageType>* temp_node;
    while (true) {
        temp_node = n->RandomNext(randomEngine);
        if (len >= maxSetting) {
            break;
        }
        else if ((temp_node == NULL) && (len < minSetting)) {
            continue;
        }
 
        else if (temp_node == NULL){
            break;
        }
            
        n = temp_node;
 
        buffer[len++] = n->NodeValue();
    }
 
    //null terminate the string
    buffer[len] = 0x00;
 
    //do something with the generated string
    return buffer; //for now
}

Save()

std::ofstream * Markov::API::MarkovPasswords::Save ( const char *  filename )

inherited

Export model to file.

Parameters

filename

- Export filename.

Returns

std::ofstream* of the exported file.

Definition at line 106 of file markovPasswords.cpp.

                                                                {
    std::ofstream* exportFile;
 
    std::ofstream newFile(filename);
 
    exportFile = &newFile;
    
    this->Export(exportFile);
    return exportFile;
}

References Markov::Model< NodeStorageType >::Export().

Here is the call graph for this function:

StarterNode()

Node<char >* Markov::Model< char >::StarterNode ( )

inlineinherited

Return starter Node.

Returns

starter node with 00 NodeValue

Definition at line 171 of file model.h.

{ return starterNode;}

Train()

void Markov::API::ModelMatrix::Train	(	const char *	datasetFileName,
		char	delimiter,
		int	threads
	)

Train the model with the dataset file.

Parameters

datasetFileName	- Ifstream* to the dataset. If null, use class member
delimiter	- a character, same as the delimiter in dataset content
threads	- number of OS threads to spawn

Markov::API::MarkovPasswords mp;
mp.Import("models/2gram.mdl");
mp.Train("password.corpus");

Construct the matrix when done.

Definition at line 25 of file modelMatrix.cpp.

                                                                                        {
    this->DeallocateMatrix();
    this->Markov::API::MarkovPasswords::Train(datasetFileName,delimiter,threads);
    this->ConstructMatrix();
}

References ConstructMatrix(), DeallocateMatrix(), and Markov::API::MarkovPasswords::Train().

Referenced by Markov::Markopy::CUDA::BOOST_PYTHON_MODULE(), and Markov::Markopy::BOOST_PYTHON_MODULE().

Here is the call graph for this function:

Here is the caller graph for this function:

TrainThread()

void Markov::API::MarkovPasswords::TrainThread ( Markov::API::Concurrency::ThreadSharedListHandler *  listhandler, char  delimiter  )

privateinherited

A single thread invoked by the Train function.

Parameters

listhandler	- Listhandler class to read corpus from
delimiter	- a character, same as the delimiter in dataset content

Definition at line 85 of file markovPasswords.cpp.

                                                                                                                  {
    char format_str[] ="%ld,%s";
    format_str[3]=delimiter;
    std::string line;
    while (listhandler->next(&line) && keepRunning) {
        long int oc;
        if (line.size() > 100) {
            line = line.substr(0, 100);
        }
        char* linebuf = new char[line.length()+5];
#ifdef _WIN32
        sscanf_s(line.c_str(), "%ld,%s", &oc, linebuf, line.length()+5); //<== changed format_str to-> "%ld,%s"
#else
        sscanf(line.c_str(), format_str, &oc, linebuf);
#endif
        this->AdjustEdge((const char*)linebuf, oc); 
        delete linebuf;
    }
}

References Markov::Model< NodeStorageType >::AdjustEdge(), keepRunning, and Markov::API::Concurrency::ThreadSharedListHandler::next().

Referenced by Markov::API::MarkovPasswords::Train().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

datasetFile

std::ifstream* Markov::API::MarkovPasswords::datasetFile

privateinherited

Definition at line 123 of file markovPasswords.h.

edgeMatrix

char** Markov::API::ModelMatrix::edgeMatrix

protected

2-D Character array for the edge Matrix (The characters of Nodes)

Definition at line 175 of file modelMatrix.h.

Referenced by ConstructMatrix(), DeallocateMatrix(), DumpJSON(), and FastRandomWalkThread().

edges

std::vector<Edge<char >*> Markov::Model< char >::edges

privateinherited

A list of all edges in this model.

Definition at line 204 of file model.h.

matrixIndex

char* Markov::API::ModelMatrix::matrixIndex

protected

to hold the Matrix index (To hold the orders of 2-D arrays')

Definition at line 190 of file modelMatrix.h.

Referenced by ConstructMatrix(), DeallocateMatrix(), DumpJSON(), and FastRandomWalkThread().

matrixSize

int Markov::API::ModelMatrix::matrixSize

protected

to hold Matrix size

Definition at line 185 of file modelMatrix.h.

Referenced by ConstructMatrix(), DeallocateMatrix(), DumpJSON(), FastRandomWalkThread(), and Markov::API::CUDA::CUDAModelMatrix::FlattenMatrix().

modelSavefile

std::ofstream* Markov::API::MarkovPasswords::modelSavefile

privateinherited

Dataset file input of our system

Definition at line 124 of file markovPasswords.h.

nodes

std::map<char , Node<char >*> Markov::Model< char >::nodes

privateinherited

Map LeftNode is the Nodes NodeValue Map RightNode is the node pointer.

Definition at line 193 of file model.h.

outputFile

std::ofstream* Markov::API::MarkovPasswords::outputFile

privateinherited

File to save model of our system

Definition at line 125 of file markovPasswords.h.

ready

bool Markov::API::ModelMatrix::ready

protected

True when matrix is constructed. False if not.

Definition at line 200 of file modelMatrix.h.

Referenced by ConstructMatrix(), DeallocateMatrix(), and ModelMatrix().

starterNode

Node<char >* Markov::Model< char >::starterNode

privateinherited

Starter Node of this model.

Definition at line 198 of file model.h.

totalEdgeWeights

long int* Markov::API::ModelMatrix::totalEdgeWeights

protected

Array of the Total Edge Weights.

Definition at line 195 of file modelMatrix.h.

Referenced by ConstructMatrix(), DeallocateMatrix(), and FastRandomWalkThread().

valueMatrix

long int** Markov::API::ModelMatrix::valueMatrix

protected

2-d Integer array for the value Matrix (For the weights of Edges)

Definition at line 180 of file modelMatrix.h.

Referenced by ConstructMatrix(), DeallocateMatrix(), DumpJSON(), and FastRandomWalkThread().

---

The documentation for this class was generated from the following files:

• Markopy/MarkovAPI/src/modelMatrix.h
• Markopy/MarkovAPI/src/modelMatrix.cpp